堆排序 - 堆(最小/最大)用于升序和降序排序?
我注意到一件非常奇怪的事情。堆排序 - 堆(最小/最大)用于升序和降序排序?
经过这个lecture后,我在C++中实现了一些堆排序代码。
代码如下。
template<typename T> void min_heapify(std::vector<T> &vec, int i, int size)
{
int left = (2*i); //left child of a zero-indexed heap (array)
int right = (2*i)+1; //right child.
int min;
min = ((left<size) && (vec[left] < vec[i])) ? left : i;
min = ((right<size) && (vec[right] < vec[min])) ? right : min;
if (min!= i)
{
swapper(vec[i],vec[min]);
min_heapify(vec, min, size);
}
}
template<typename T> void build_min_heap(std::vector<T> &vec, int size)
{
int i = size/2;
while(i--)
{
min_heapify(vec, i, size);
}
}
template<typename T> void heap_sort(std::vector<T> &vec, int size)
{
// build min heap
build_min_heap(vec, size);
// then extract min repeatedly.
while(size>0)
{
size--;
swapper(vec[0],vec[size]);
min_heapify(vec,0,size);
}
}
int main()
{
vector<int> v{14,-1,1000, -999, 3,2,5,10};
heap_sort(v, v.size());
return 0;
}
奇特的是,它是有意义的,我认为 - 建立一个最小堆 - 提取分钟(或建立一个最小堆后在根执行最小heapify) 应导致升序。 但是,在执行此代码,并打印出合成矢量后, 我得到:
1000 14 10 5 3 2 -1 -999
,同时努力使正在发生的事情的感觉,我改变
min = ((left<size) && (vec[left] < vec[i])) ? left : i;
min = ((right<size) && (vec[right] < vec[min])) ? right : min;
到
min = ((left<size) && (vec[left] > vec[i])) ? left : i;
min = ((right<size) && (vec[right] > vec[min])) ? right : min;
这实际上最终选择较大(或最大)的父节点和子节点,结果矢量为:
-999 -1 2 3 5 10 14 1000
我做错了什么或者是我对堆/堆类的理解不清楚吗?我在这里错过了什么?
是的swapper(vec[0],vec[size]);
是提取。 您正将第一个元素提取到矢量的最后一个元素中。因此得到相反的结果。
堆最小元素是vec[0]
。将其交换到最后位置将在该向量内创建一个从最大到最小的排序。
如果要实现像
result.push_back(heap.pop_min());
你会得到您所期望的顺序。
*“你应该提取......(推入结果向量)”* - 你呢?这听起来像不必要的工作,如果你想要的是一个就地排序。你应该改变你对堆排序应该如何工作的期望,并且如果你想要颠倒结果,那么使用反向比较。 –
@BenjaminLindley感谢您的评论。我会修改。 –
@BenjaminLindley嗨,这是否意味着,我应该诉诸使用最大heapify为了做 - 升序排序就地? – Raaj
您对heapsort中的堆使用情况的理解可能不够有效:通常会将值从最后选择到最先。 – greybeard