堆（Heap）的实现

这次实现了堆，这个堆不是指系统堆栈的堆，是一种数据结构，见下图

堆的本质就是一个数组（上图中，红色的是值，黑色的是下标）简单的来说就是把一个数组看成是二叉树，就像上图

大堆和小堆分别是指根节点比孩子节点的值大或者是小，看了上图之后就可以发现，父亲节点和孩子节点之间下表的关系，parnet=(child-1)/2

利用这个关系就可以实现堆了，堆的基本方法有构造，析构，插入，删除，像大堆小堆这样特殊的堆肯定是要有调整函数来保持他们的特性的，所以我还写了向上调整和向下调整的函数

为了让大堆和小堆之间切换自如（就是方便维护），我写了两个仿函数，建立堆的对象时传个模版参数就好了

  1 #pragma once
  2 #include<iostream>
  3 #include<vector>
  4 using namespace std;
  5 
  6 template<class T>
  7 struct Less
  8 {
  9     bool  operator()(const T& l,const T& r)
 10     {
 11         return l < r;
 12     }
 13 };
 14 
 15 template<class T>
 16 struct Greater
 17 {
 18     bool operator()(const T& l ,const T& r)
 19     {
 20         return l > r;
 21     }
 22 };
 23 
 24 
 25 
 26 
 27 
 28 template<class T, class Compare = Less<T>>
 29 class Heap
 30 {
 31 public:
 32     Heap()
 33     {
 34 
 35     }
 36     Heap(vector<T> a)
 37         :array(a)
 38     {
 39         for (int i = (array.size() - 2) / 2; i >=0 ; --i)
 40         {
 41             AdjustDown(i);
 42         }
 43     }
 44     Heap(T *a, size_t size)
 45     {
 46         for (int i = 0; i < size; ++i)
 47         {
 48             array.push_back(a[i]);
 49         }
 50         for (int i = (array.size() - 2) / 2; i >= 0; --i)
 51         {
 52             AdjustDown(i);
 53         }
 54     }
 55     ~Heap()
 56     {
 57         
 58     }
 59     void Push(T x)
 60     {
 61         array.push_back(x);
 62         AdjustUp(array.size()-1);
 63     }
 64     void Pop()
 65     {
 66         swap(array.front(), array.back());
 67         array.pop_back();
 68         AdjustDown(0);
 69     }
 70     void AdjustDown(int root)
 71     {
 72         int child = root * 2 + 1;
 73         while (child < array.size())
 74         {
 75             if (child + 1 < array.size() && Compare()(array[child + 1], array[child]))
 76             {
 77                 child++;
 78             }
 79             if (Compare(array[root], array[child]))
 80             {
 81                 swap(array[root], array[child]);
 82                 root = child;
 83                 child = root * 2 + 1;
 84             }
 85             else
 86             {
 87                 break;
 88             }
 89         }
 90     }
 91     void AdjustUp(int child)
 92     {
 93         int parent = (child - 1) / 2;
 94         while (child > 0)
 95         {
 96             if (Compare()(array[child], array[parent]))
 97             {
 98                 swap(array[child], array[parent]);
 99                 child = parent;
100                 parent = (child - 1) / 2;
101             }
102             else
103             {
104                 break;
105             }
106         }
107     }
108     void Print()
109     {
110         for (int i = 0; i < array.size(); ++i)
111         {
112             cout << array[i] << " ";
113         }
114         cout << endl;
115     }
116     int Size()
117     {
118         return array.size();
119     }
120 protected:
121     vector<T> array;
122 };
123 
124 
125 void TestHeap()
126 {
127     Heap<int> hp;
128     int a[10] = { 5,3,6,2,1,7,8,9,4,0 };
129     for (int i = 0; i < 10; ++i)
130     {
131         hp.Push(a[i]);
132     }
133     hp.Print();
134 }

当一个一个push插入的时候我们只需要把这个元素插入到数组的最后，然后顺着二叉树向上调整就可以了（只需要调整这一条线）

删除头元素（根节点）的时候，为了不破坏结构，我们选择先跟处于最后位置的元素交换，之后在末尾删除掉“根节点”，然后因为最大值（最小值）被换到了根节点，不符合小堆（大堆）的结构要求，只需要顺着这条路一直向下调整就可以了

我还写了一个构造函数接收的参数是一个vector，这是把整个vector调整成大堆（小堆），先找到最后一个元素的父亲节点，一直往前向下调整就可以了，因为这个父亲节点之前也肯定都是有孩子父亲节点