堆：是一種數組對象，它可以被看成是一種二叉樹結構。

我們把堆的二叉樹存儲方式分為兩種：即大堆和小堆。那么問題來了，什么大堆？什么是小堆？

大堆：讓每個父節點的值都大于孩子節點的值。

小堆：讓每個父節點的值都小于孩子節點的值。

說完概念后，就來考慮一下如何來實現大堆和小堆吧。第一步肯定得有一個堆吧，所以我們首先得建堆，這是毋庸置疑的。由于堆實際上就是一個二叉樹結構，所以先將數壓進棧中，然后通過向下調整來建大堆。

第一例：堆的實現

具體實現代碼如下：

#pragma once 
#include<vector>
#include<iostream>
#include<assert.h>
using namespace std;

//仿函數用于下面的父節點與子節點的比較
template<class T>
struct Less
{bool operator()(const T& left,const T& right){return (left < right);}};template<class T>
struct Greater
{bool operator()(const T& left,const T& right){return (left > right);}};template<class T,class  Compare = Greater<T>>
class Heap
{
public:

<span style="white-space:pre">	</span>//建堆Heap(const T* a,size_t size){assert(a);for(size_t i = 0; i < size; i++){_a.push_back(a[i]);}for(size_t i = (_a.size()-2)/2; i > 0; i--){AdjustDown(i);}}void push(const T& x){_a.push_back(x);AdjustUp(_a.size()-1);}void pop(){assert(!_a.empty());swap(_a[0],_a[_a.size()-1]);_a.pop_back();AdjustDown(0);}bool Empty(){return _a.empty();}size_t Size(){return _a.size();}void print(){for(size_t i = 0; i < _a.size(); i++){cout<<_a[i]<<" ";}cout<<endl;}
protected:

<span style="white-space:pre">	</span>//向下調整void AdjustDown(size_t parent){size_t child = parent*2+1;Compare com;while(child < _a.size()){if(child+1 < _a.size() && com(_a[child+1],_a[child])){child++;}if(com(_a[child],_a[parent]))     //孩子節點大于父節點{swap(_a[child],_a[parent]);parent = child;child = parent*2+1;}else{break;}}}<span style="white-space:pre">	</span>//向上調整void AdjustUp(size_t child){size_t parent = (child-1)/2;Compare com;while(child > 0){if(com(_a[child],_a[parent]))      //父節點小于孩子節點{swap(_a[child],_a[parent]);child = parent;parent = (child-1)/2;}else{break;}}}
protected:vector<T> _a;
};
void testHeap()
{int a[] = {10,11, 13, 12, 16, 18, 15, 17, 14, 19};Heap<int,Greater<int>> hp(a,sizeof(a)/sizeof(a[0]));hp.push(2);hp.print();
}

第二例：

同樣，我們也可以實現堆排序：

如圖實現方式：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? （1）

（2）

? ??? ? ?

（3）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ...

依此向下調整的方式進行排序。

void AdjustDown(int a[],int n, int parent){int child = parent*2+1;while(child < n){if(child+1 < n && a[child+1] > a[child]){child++;}if(a[child] > a[parent]){swap(a[child],a[parent]);parent = child;child = parent*2+1;}else{break;}}}void HeapSort(int a[],size_t n){assert(a);for(int i = (n-2)/2; i >= 0; --i){AdjustDown(a,n,i);}for(int i = 0; i < n; ++i){ swap(a[0],a[n-1-i]);             //交換堆頂元素和最后一個元素AdjustDown(a,n-1-i,0);           //將最后一個元素固定，向下調整前n-i-1個}}void print(int a[],size_t size){for(size_t i = 0; i < size;i++){cout<<a[i]<<" ";}cout<<endl;}

	void TestHeapSort()
{int a[] = {2,1,4,5,0,6,3,7,8,9};HeapSort(a, sizeof(a)/sizeof(a[0]));print(a,sizeof(a)/sizeof(a[0]));
}

堆的實現及堆排序就說到這里啦。。堆排序將會在后期排序那部分再與大家見面哦。到時候會與其他排序一起比較，包括它的時間復雜度和空間復雜度，以及各個排序算法的優缺點。今天的就說到這里啦~~