堆排序算法原理
堆排序算法，就是利用二叉树的原理，我们知道，对于二叉树而言，具有一定的排序性质：
如 左节点是小于根节点的值，右节点的值肯定是大于根节点的值的，因此， 我们算是快能找到某一个元素
因为如果当前元素比要找的元素要大，那么就往右走，如果当前元素比要找的元素要小，那么往右找，呵呵，相
信如何树上存在这号元素的话，应该很快就能找到。
引申到堆排序
那么堆就是一棵完全“二叉树”，只是形似而己了。
根据以上性质，因为要结点是整个树中最大（小）的元素，那么如果给我一棵二叉树，就可以很得到它的最大（小）值啰。
想想，如果我们每次建立一个堆后，将它的根拿出来，然后用剩下的元素再建一棵二叉树，那是不是就可以排序了呢？
因为第一次建立一棵二叉树，然后拿到它的根，然后将剩下的元素再建一棵二叉树，那么现在的根就是上一次剩下的元素中间
最大（小）的元素了呢。嗯。这是肯定的。依次下去，拿出的根结点元素就己经排好序了啊。
那废话不多说，如何实现呢？看代码得了：
主代码：
#ifndef HEAP_SORT_H#define HEAP_SORT_H#include<iostream>#include<string>template<class Type>class HeapSort{private: Type *ptr; int Length; int HeapSize; public: int rightHeap(int i){ return 2*i+1; } int leftHeap(int i){ return 2*i+2; } HeapSort(Type *p,int Len){ this->ptr=p; this->Length=Len; this->HeapSize=Len; } void maxHeapy(int idx){ int right=rightHeap(idx); int left=leftHeap(idx); int maxIdx=idx; if(right<HeapSize&&ptr[right]>ptr[idx]){ maxIdx=right; } if(left<HeapSize&&ptr[left]>ptr[maxIdx]){ maxIdx=left; } if(maxIdx!=idx){ Type temp=ptr[idx]; ptr[idx]=ptr[maxIdx]; ptr[maxIdx]=temp; maxHeapy(maxIdx); } } void buildMaxHeapy(){ for(int i=HeapSize/2+2; i>=0;i--){ maxHeapy(i); } } void heapSort(){ for(int i=Length-1;i>0;i--){ buildMaxHeapy(); //建立堆 Type temp=ptr[i]; ptr[i]=ptr[0]; ptr[0]=temp; --HeapSize; } }}; #endif
代码部分解释：
左右孩子问题：
int rightHeap(int i){ return 2*i+1; }int leftHeap(int i){ return 2*i+2;}
上面的代码的主要作用是求左右孩子了啊，那么为什么是2*i+1和2*i+2而不是2*i和2*i+1,
问得好，我也是曾经在这上面栽过跟头的啊，首先我们的下标是从0开始啦 ，那么如果下标i取0的时候，那是不是2*i=0,也就是孩子和根的下标相等了，那是
不行的。代码就有BUG了。但是如果对一些下标从1开始的数组，那么
2*i和2*i+1也是可以的。
维护最大堆性质：
void maxHeapy(int idx){ int right=rightHeap(idx); int left=leftHeap(idx); int maxIdx=idx; if(right<HeapSize&&ptr[right]>ptr[idx]){ maxIdx=right; } if(left<HeapSize&&ptr[left]>ptr[maxIdx]){ maxIdx=left; } if(maxIdx!=idx){ Type temp=ptr[idx]; ptr[idx]=ptr[maxIdx]; ptr[maxIdx]=temp; maxHeapy(maxIdx); } }
上面代码的主要作用就是对某一个堆的下票idx节点，我们要求它下面的节点维护“堆”的性质，如何维护呢？无非就是使根、右，左孩子
三个中，使得根节点取得它们中的最大值啰。哈哈。。好简单。，嗯。。还是有些小问题。可能是我太笨。
if(right<HeapSize&&ptr[right]>ptr[idx]){ maxIdx=right; }if(left<HeapSize&&ptr[left]>ptr[maxIdx]){ maxIdx=left; }
不是
if(right<HeapSize&&ptr[right]>ptr[idx]){ maxIdx=right; }if(left<HeapSize&&ptr[left]>ptr[idx]){ maxIdx=left; }
好好想想两者的差别。这里搞不对，问题就大。当然
if(maxIdx!=idx){ Type temp=ptr[idx]; ptr[idx]=ptr[maxIdx]; ptr[maxIdx]=temp; maxHeapy(maxIdx); }
这里的是因为你调换了其中的两个元素，可能以前就只有这两个元素破坏了堆的性质，其它的都 可以，但下因为你的调换使得调换后下面的堆
性质又破坏了，因此，还是得下维护其性质啊。
在上面的代码中，还存在一非常关键的问题：
if(right<HeapSize&&ptr[right]>ptr[idx]){ maxIdx=right; }if(left<HeapSize&&ptr[left]>ptr[maxIdx]){ maxIdx=left; }
这是正好限制了下标的取值范围。
建堆
void buildMaxHeapy(){ for(int i=HeapSize/2; i>=0;i--){ maxHeapy(i); }}
为什么是
for
(
int
i
=
HeapSize
/
2
;
i
>=
0
;
i
--)，而不是
for
(
int
i
=
HeapSize
;
i
>=
0
;
i
--)呢？
因为
也就是能省就省吧。反正你浪费也没办法。
堆排序
void heapSort(){ for(int i=Length-1;i>0;i--){ buildMaxHeapy(); //建立堆 Type temp=ptr[i]; ptr[i]=ptr[0]; ptr[0]=temp; --HeapSize; }
就是每次把最大（小）的元素拿出来啦，然后缩短堆大小，再建堆。。。。。。。。
所以堆排序算法的主要步步骤：
左右孩子问题-> 维护最大堆性质 ->建堆->堆排序
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655561.html
相关资源：数据结构—成绩单生成器
