這次實現了堆，這個堆不是指系統堆棧的堆，是一種數據結構，見下圖
堆的本質就是一個數組（上圖中，紅色的是值，黑色的是下標）簡單的來說就是把一個數組看成是二叉樹，就像上圖
大堆和小堆分別是指根節點比孩子節點的值大或者是小，看了上圖之後就可以發現，父親節點和孩子節點之間下表的關系，parnet=(child-1)/2
利用這個關系就可以實現堆了，堆的基本方法有構造，析構，插入，刪除，像大堆小堆這樣特殊的堆肯定是要有調整函數來保持他們的特性的，所以我還寫了向上調整和向下調整的函數
為了讓大堆和小堆之間切換自如（就是方便維護），我寫了兩個仿函數，建立堆的對象時傳個模版參數就好了
#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Less
{
bool operator()(const T& l,const T& r)
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l ,const T& r)
{
return l > r;
}
};
template<class T, class Compare = Less<T>>
class Heap
{
public:
Heap()
{
}
Heap(vector<T> a)
:array(a)
{
for (int i = (array.size() - 2) / 2; i >=0 ; --i)
{
AdjustDown(i);
}
}
Heap(T *a, size_t size)
{
for (int i = 0; i < size; ++i)
{
array.push_back(a[i]);
}
for (int i = (array.size() - 2) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
~Heap()
{
}
void Push(T x)
{
array.push_back(x);
AdjustUp(array.size()-1);
}
void Pop()
{
swap(array.front(), array.back());
array.pop_back();
AdjustDown(0);
}
void AdjustDown(int root)
{
int child = root * 2 + 1;
while (child < array.size())
{
if (child + 1 < array.size() && Compare()(array[child + 1], array[child]))
{
child++;
}
if (Compare(array[root], array[child]))
{
swap(array[root], array[child]);
root = child;
child = root * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (Compare()(array[child], array[parent]))
{
swap(array[child], array[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void Print()
{
for (int i = 0; i < array.size(); ++i)
{
cout << array[i] << " ";
}
cout << endl;
}
int Size()
{
return array.size();
}
protected:
vector<T> array;
};
void TestHeap()
{
Heap<int> hp;
int a[10] = { 5,3,6,2,1,7,8,9,4,0 };
for (int i = 0; i < 10; ++i)
{
hp.Push(a[i]);
}
hp.Print();
}
當一個一個push插入的時候我們只需要把這個元素插入到數組的最後，然後順著二叉樹向上調整就可以了（只需要調整這一條線）
刪除頭元素（根節點）的時候，為了不破壞結構，我們選擇先跟處於最後位置的元素交換，之後在末尾刪除掉“根節點”，然後因為最大值（最小值）被換到了根節點，不符合小堆（大堆）的結構要求，只需要順著這條路一直向下調整就可以了
我還寫了一個構造函數接收的參數是一個vector，這是把整個vector調整成大堆（小堆），先找到最後一個元素的父親節點，一直往前向下調整就可以了，因為這個父親節點之前也肯定都是有孩子父親節點