堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

这是一个普通的堆，我们想把它变成最大堆，就必须了解最大堆的特点。然后我们对它进行调整，保证每个父节点的都大于孩子节点。

我们先调整这个二叉树的一部分，从它的最后一个节点开始调整，图中红色箭头开始调整，如果父节点小于孩子节点，就交换，否则结束。在看下一个节点，一直这样循环，直到全部调整完。

代码如下：

void _AdjustDown(size_t parent, size_t size){size_t child = 2 * parent + 1;while (child < size){//child + 1 < size保证是最后一个节点if (child + 1 < size&&_arr[child] < _arr[child + 1]){child++;//孩子节点最大的一个节点}//交换if (_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}

如果想把它调整成最小堆，必须符合每个父节点的都小于孩子节点，代码原理和最大堆相似。

代码如下：

void _AdjustUp(int child){int parent = (child - 1) / 2;int size = _arr.size();while (child > 0){if (_arr[child] > _arr[parent]){swap(_arr[child], _arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

下面我给出完整代码，构造函数用的是调整成大堆。为了让代码更简洁，实现过程借用了库函数中的vector。

代码如下：

Heap.h中

#include<assert.h>
#include <vector>
template <class T>
class Heap
{
public:Heap():_arr(NULL){}//构造函数Heap(const T*arr, size_t size){_arr.reserve(size);for (size_t i = 0; i < size; i++){_arr.push_back(arr[i]);}for (int j = (_arr.size() - 2) / 2; j >= 0; j--){_AdjustDown(j, size);}}//拷贝构造Heap(const vector<T>& h){_arr.reserve(_arr.size());for (size_t i = 0; i < _arr.size(); i++){_arr.push_back(h[i]);}}//先储存在顺序表中，在进行下调void push(const T& x){_arr.push_back(x);_AdjustUp(_arr.size()-1);}//删除void pop(){size_t size = _arr.size();assert(size > 0);swap(_arr[0], _arr[size - 1]);//先把根结点和要删除的结点交换_arr.pop_back();//然后删除size = _arr.size();_AdjustDown(0, size);//最后上调}//堆是否为空bool Empty(){size_t size = _arr.size();assert(size >= 0);return size == 0;}//堆的大小size_t Size(){size_t size = _arr.size();assert(size >= 0);return size;}//访问根结点T& Top(){size_t size = _arr.size();assert(size > 0);return _arr[0];}void Print(){for (int i = 0; i < Size(); i++){cout << _arr[i] << " ";}cout << endl;}
protected://下调void _AdjustDown(size_t parent, size_t size){size_t child = 2 * parent + 1;while (child < size){//child + 1 < size保证是最后一个节点if (child + 1 < size&&_arr[child] < _arr[child + 1]){child++;//孩子节点最大的一个节点}//交换if (_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}//上调void _AdjustUp(int child){int parent = (child - 1) / 2;int size = _arr.size();while (child > 0){if (_arr[child] > _arr[parent]){swap(_arr[child], _arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}
protected:vector<T> _arr;
};

test.cpp中

#include<iostream>
using namespace std;
#include"Heap.h"
void Test()
{int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };Heap<int> h(a, sizeof(a) / sizeof(a[0]));h.Print();h.push(20);h.Print();h.pop();h.Print();Heap<int> h1(h);h1.Print();
}
int main()
{Test();system("pause");return 0;
}