堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
堆结构的二叉树存储:
大堆:每个父节点的都大于孩子节点;小堆:每个父节点的都小于孩子节点。
建堆:由于堆被视为完全二叉树,故在h-1层找到第一个(从后往前找)非叶子结点,进行堆的下调
建大堆时,从下往上依次判断并调整堆,使该结点的左右子树都满足大堆
建小堆时,从下往上依次判断并调整堆,使该结点的左右子树都满足小堆
可见大堆的建立与小堆的建立方式类似,下面以大堆进行讨论。
利用vactor模板存储堆中元素
templateclass Heap{public: Heap(); Heap(const T* a, size_t size); void Push(const T& x); void Pop(); T& GetTop();//访问堆顶元素 bool Empty();//判空 size_t Size();//堆元素个数 void PrintHeap();protected: void _AdjustDown(size_t Parent);//下调--建大堆(每个父结点都大于孩子结点) void _AdjustUp(size_t Child);//上调--建小堆(每个父结点都小于孩子结点)private: vector _a;};
实现堆的建立
templateHeap ::Heap():_a(NULL){}template Heap ::Heap(const T* a, size_t size){ assert(a); _a.reserve(size);//初始化_a(vector模板的使用) for (size_t i = 0; i < size; ++i) { _a.push_back(a[i]); } 堆的第一个非叶子结点的数组下标时((size-1)-1)/2(最后一个结点是size-1) for (int i = (int)(size - 2) / 2; i >= 0; --i)//不能定义为size_t(无符号) { _AdjustDown(i); } //建小堆,类似建大堆的方式,从下向上进行调整堆,使该结点处的左右子树都满足小堆 //在进行调小堆时,也通过下调实现}//下调--建大堆/小堆template void Heap ::_AdjustDown(size_t Parent){ size_t Child = Parent * 2 + 1; while (Child < _a.size()) {//先进行左右结点的比较,使Child为较大的数的下标,然后与父亲结点进行比较,使较大的数据为父亲结点 if (Child + 1 < _a.size() && _a[Child] < _a[Child + 1])//存在右结点再进行比较 { ++Child; } if (_a[Child] > _a[Parent])//如果子结点大于父亲结点就交换,否则就要跳出循环 { swap(_a[Child], _a[Parent]); Parent = Child; Child = Parent * 2 + 1; } else { break; } }}//在建立小堆时,只需要将比较条件进行改变就可以实现
在已经是大堆或小堆的堆中加入元素使堆仍为大堆,可通过该元素与它的父结点进行比较
ps:由于插入的元素在数组末尾,故需要通过上调进行比较实现堆的大堆或小堆
templatevoid Heap ::_AdjustUp(size_t Child)//上调{ size_t Parent = (Child - 1) / 2;//结点为Child的父亲结点为(Child-1)/2 while (Child > 0)//当Child等于0时以到堆顶,终止循环 { if (_a[Parent] < _a[Child])//直接进行父亲结点和子结点的比较 { swap(_a[Child], _a[Parent]); Child = Parent; Parent = (Child - 1) / 2; } else { break; } }}template void Heap ::Push(const T& x)//元素x入堆{ //_a.resize(_a.size() + 1); //_a[_a.size()-1] = x; _a.push_back(x); _AdjustUp(_a.size() - 1);}
堆中pop元素,删除堆顶元素,使堆仍为大堆。
在已经是大堆或小堆的堆中删除堆顶元素,直接删除堆顶元素,造成无法进行大堆或小堆的实现,可通过将第一个元素与最后一个元素进行交换,然后删除最后一个元素,最后通过下调实现大堆或小堆
templatevoid Heap ::Pop()//出堆{ size_t size = _a.size(); assert(size > 0);//断言堆非空 swap(_a[0], _a[size - 1]); _a.pop_back(); _AdjustDown(0);//从堆顶开始进行下调}
实现堆的堆顶,判空及堆元素个数
templateT& Heap ::GetTop()//访问堆顶元素{ return _a[0];}template bool Heap ::Empty()//判空{ return _a.size() == 0;}template size_t Heap ::Size()//堆元素个数{ return _a.size();}template void Heap ::PrintHeap(){ for (size_t i = 0; i < _a.size(); ++i) { cout << _a[i] << " "; } cout << endl;}
测试用例
#include"Heap.hpp"void Test4(){ int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19}; Heap h(arr, sizeof(arr) / sizeof(arr[0])); h.PrintHeap(); cout << "empty: " << h.Empty() << endl; cout << "size: " << h.Size() << endl; cout << "gettop: " << h.GetTop() << endl; h.Push(20); h.PrintHeap(); h.Pop(); h.PrintHeap();}
如果对于上述说明还是不是很清楚,可自己亲手画图分析,存在不足之处请多多指教。
【vector】包含着一系列连续存储的元素, 其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。