排序算法之（7）——堆排序

【堆排序的思路】

堆排序主要是利用了堆的性質。對于大頂堆：堆中的每一個節點的值都不小于它的孩子節點的值，具體可參考我的還有一篇博客http://blog.csdn.net/adminabcd/article/details/46880591，那么大頂堆的堆頂元素就是當前堆中全部元素中最大的。

利用這個性質。進行例如以下操作，則能夠得到一個有序序列：

1. 將待排序的n個元素一個一個插入堆中，那么此時堆頂元素就是全部元素中最大的
2. 將堆頂元素取出，剩下的n-1個元素組成新的堆，新堆的堆頂元素是當前堆中元素中最大的，也就是全部元素中第二大的。

3. 將堆頂元素取出。剩下的n-2個元素組成新的堆，新堆的堆頂元素是當前堆中元素中最大的。也就是全部元素中第三大的。
   .
   .
   .
   .

4. 直到全部元素取出，此時全部取出元素序列就是一個從大到小的有序序列。

【代碼實現】

1. 大頂堆的實現

#ifndef maxheap_h
#define maxheap_h
template<class T>
class Maxheap
{
public:Maxheap(int size);~Maxheap();bool Isempty();void push(T item);  //插入操作void pop();  //刪除操作T top();
private:T *heap;int currentSize;int capacity;
};
//-------構造函數初始化-------
template<class T>
Maxheap<T>::Maxheap(int size)
{if(size<1){throw"capacity must be >=1";}else{currentSize=0;capacity=size;heap=new T[capacity+1]; //heap[0]不使用}
}
//-------析構函數釋放空間-------
template<class T>
Maxheap<T>::~Maxheap()
{delete []heap;
}
//--------推斷堆是否為空-------
template<class T>
bool Maxheap<T>::Isempty()
{return currentSize==0;
}
//---------獲取最大元素----------
template<class T>
T Maxheap<T>::top()
{return heap[1];
}
//-------插入操作-----
template<class T>
void Maxheap<T>::push(T item)
{if(currentSize==capacity)throw"Maxheap is full";else{currentSize++;int currentNode=currentSize;// 元素的插入位置初始化為最后while(currentNode>1&&heap[currentNode/2]<item)  //(從下往上)進行調整{heap[currentNode]=heap[currentNode/2];currentNode=currentNode/2;}heap[currentNode]=item; //插入元素}
}//-----刪除操作-------
template<class T>
void Maxheap<T>::pop()
{if(Isempty())throw"heap is empty ,cannot delete";else{T last=heap[currentSize];  //將最后一個元素初始化為根currentSize--;int currentNode=1;       int child=2;while(child<=currentSize)  //（從上往下）進行調整{if(child<currentSize&&heap[child]<heap[child+1])child++;if(last>=heap[child])break;else{heap[currentNode]=heap[child];currentNode=child;child=child*2;}}heap[ currentNode]=last; }
}
#endif

1. 堆排序實現

#include"MAXHEAP.h"
#include<iostream>
using namespace std;
int main()
{Maxheap<int> H(100);int arr[]={50,15,30,70,6};for(int i=0;i<5;i++){H.push(arr[i]); //元素進堆}for(int i=0;i<5;i++){arr[i]= H.top();H.pop();  //取出堆頂元素。其余元素組成新的堆}cout<<"降序排序:";for(int i=0;i<5;i++){cout<<arr[i]<<" ";}cout<<endl;cout<<"升序排序:";for(int i=4;i>=0;i--){cout<<arr[i]<<" ";}cout<<endl;system("pause");return 0;
}

【結果】