十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
创新互联从2013年开始,先为雁江等服务建站,雁江等地企业,进行企业商务咨询服务。为雁江企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。堆结构的二叉树存储是
这是一个普通的堆,我们想把它变成大堆,就必须了解大堆的特点。然后我们对它进行调整,保证每个父节点的都大于孩子节点。
我们先调整这个二叉树的一部分,从它的最后一个节点开始调整,图中红色箭头开始调整,如果父节点小于孩子节点,就交换,否则结束。在看下一个节点,一直这样循环,直到全部调整完。
代码如下:
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#include template 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 & 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 _arr; };
test.cpp中
#includeusing namespace std; #include"Heap.h" void Test() { int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 }; Heap h(a, sizeof(a) / sizeof(a[0])); h.Print(); h.push(20); h.Print(); h.pop(); h.Print(); Heap h2(h); h2.Print(); } int main() { Test(); system("pause"); return 0; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。