C++中的堆排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7520133/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Heap Sort in C++
提问by Siddharth
Okay, so after struggling with trying to debug this, I have finally given up. I'm a beginner in C++ & Data Structures and I'm trying to implement Heap Sort in C++. The code that follows gives correct output on positive integers, but seems to fail when I try to enter a few negative integers.
好吧，在努力调试这个之后，我终于放弃了。我是 C++ 和数据结构的初学者，我正在尝试用 C++ 实现堆排序。下面的代码在正整数上给出了正确的输出，但是当我尝试输入几个负整数时似乎失败了。
Please point out ANY errors/discrepancies in the following code. Also, any other suggestions/criticism pertaining to the subject will be gladly appreciated.
请指出以下代码中的任何错误/差异。此外，与该主题有关的任何其他建议/批评将不胜感激。
//Heap Sort
#include <iostream.h>
#include <conio.h>
int a[50],n,hs;
void swap(int &x,int &y)
{
int temp=x;
x=y;
y=temp;
}
void heapify(int x)
{
int left=(2*x);
int right=(2*x)+1;
int large;
if((left<=hs)&&(a[left]>a[x]))
{
large=left;
}
else
{
large=x;
}
if((right<=hs)&&(a[right]>a[large]))
{
large=right;
}
if(x!=large)
{
swap(a[x],a[large]);
heapify(large);
}
}
void BuildMaxHeap()
{
for(int i=n/2;i>0;i--)
{
heapify(i);
}
}
void HeapSort()
{
BuildMaxHeap();
hs=n;
for(int i=hs;i>1;i--)
{
swap(a[1],a[i]);
hs--;
heapify(1);
}
}
void main()
{
int i;
clrscr();
cout<<"Enter length:\t";
cin>>n;
cout<<endl<<"Enter elements:\n";
for(i=1;i<=n;i++) //Read Array
{
cin>>a[i];
}
HeapSort();
cout<<endl<<"Sorted elements:\n";
for(i=1;i<=n;i++) //Print Sorted Array
{
cout<<a[i];
if(i!=n)
{
cout<<"\t";
}
}
getch();
}
I've been reading up on Heap Sort but I'm not able to grasp most of the concept, and without that I'm not quite able to fix the logical error(s) above.
我一直在阅读堆排序，但我无法掌握大部分概念，否则我无法修复上面的逻辑错误。
回答by Karoly Horvath
You set hsafter calling BuildMaxHeap. Switch those two lines.
hs调用后设置BuildMaxHeap。切换那两条线。
hs=n;
BuildMaxHeap();
回答by Frigo
When I implemented my own heapsort, I had to be extra careful about the indices; if you index from 0, children are 2x+1 and 2x+2, when you index from 1, children are 2x and 2x+1. There were a lot of silent problems because of that. Also, every operation needs a single well-written siftDown function, that is vital.
当我实现自己的堆排序时，我必须格外小心索引；如果您从 0 开始索引，则子项是 2x+1 和 2x+2，当您从 1 开始索引时，子项是 2x 和 2x+1。因此，有很多无声的问题。此外，每个操作都需要一个编写良好的 siftDown 函数，这很重要。
Open up Wikipedia at the Heapsort and Binary heap articles and try to rewrite it more cleanly, following terminology and notation where possible. Here is my implementationas well, perhaps it can help.
在 Heapsort 和 Binary heap 文章中打开 Wikipedia 并尝试更干净地重写它，尽可能遵循术语和符号。这也是我的实现，也许它可以提供帮助。
Hmmm now that I checked your code better, are you sure your siftDown/heapify function restricts sifting to the current size of the heap?
嗯，既然我更好地检查了您的代码，您确定您的 siftDown/heapify 函数将筛选限制为堆的当前大小吗？
Edit: Found the problem! You do not initialize hsto nbefore calling BuildMaxHeap().
编辑：发现问题！在调用 BuildMaxHeap() 之前不要初始化hs为n。
回答by Pabitra Padhy
Here's an example if it helps.
如果有帮助，这里有一个例子。
#include <iostream>
#include <vector>
using namespace std;
void max_heapify(std::vector<int>& arr, int index, int N) {
// get the left and right index
int left_index = 2*index + 1;
int right_index = 2*index + 2;
int largest = 0;
if (left_index < N && arr[left_index] > arr[index]) {
// the value at the left_index is larger than the
// value at the index of the array
largest = left_index;
} else {
largest = index;
}
if (right_index < N && arr[right_index] > arr[largest]) {
// the value at the right_index is larger than the
// value at the index of the array
largest = right_index;
}
// check if largest is still the index, if not swap
if (index != largest) {
// swap the value at index with value at largest
int temp = arr[largest];
arr[largest] = arr[index];
arr[index] = temp;
// once swap is done, do max_heapify on the index
max_heapify(arr, largest, N);
}
}
void build_max_heap(std::vector<int>& arr, int N) {
// select all the non-leaf except the root and max_heapify them
for (int i = N/2 - 1; i >= 0; --i) {
max_heapify(arr, i, N);
}
}
void heap_sort(std::vector<int>& arr) {
int N = arr.size();
int heap_size = N;
// build the max heap
build_max_heap(arr, N);
// once max heap is built,
// to sort swap the value at root and last index
for (int i = N - 1; i > 0; --i) {
// swap the elements
int root = arr[0];
arr[0] = arr[i];
arr[i] = root;
// remove the last node
--heap_size;
// perform max_heapify on updated heap with the index of the root
max_heapify(arr, 0, heap_size);
}
}
int main() {
std::vector<int> data = {5,1,8,3,4,9,10};
// create max heap from the array
heap_sort(data);
for (int i : data) {
cout << i << " ";
}
return 0;
}
回答by user10733968
# include <iostream> //Desouky//
using namespace std;
void reheapify(int *arr, int n, int i)
{
int parent = i; // initilaize largest as parent/root
int child1 = 2 * i + 1; // to get first chid
int child2 = 2 * i + 2; // to get second child
if (child1 < n && arr[child1] > arr[parent]) // if child2 > parent
{
parent = child1;
}
//if child > the parent
if (child2 < n && arr[child2] > arr[parent])
{
parent = child2;
}
// if the largest not the parent
if (parent != i)
{
swap(arr[i], arr[parent]);
// Recursively heapify the affected sub-tree
reheapify(arr, n, parent);
}
}
void heapsort(int *arr, int n)
{
// build a heap
for (int i = n - 1; i >= 0; i--)
{
reheapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
reheapify(arr, i, 0);
}
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
heapsort(arr, n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
回答by Mark B
I suspect it's because you're 1-basing the array. There's probably a case where you're accidentally 0-basing it but I can't spot it in the code offhand.
我怀疑这是因为你是基于 1 的数组。可能有一种情况，您不小心将其设为 0，但我无法在代码中发现它。
