堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
最大堆:每个父节点的都大于孩子节点。
最小堆:每个父节点的都小于孩子节点。
堆结构的二叉树存储是:
代码实现如下:
#pragma once #include <iostream> #include <vector> #include <assert.h> using namespace std; //仿函数 template <typename T> struct Greater { bool operator() (const T & l, const T & r) { return l > r; } }; template <typename T> struct Less { bool operator() (const T & l, const T & r) { return l < r; } }; //模板参数 template <typename T,typename comer=Greater<T> > class Heap { public: //无参构造函数 Heap() :_a(NULL) {} //有参构造函数 Heap(T * a, size_t size) { assert(a); //先把数据保存在vector中 for (size_t i = 0; i < size; i++) { _a.push_back(a[i]); } //建堆 for (int j = ((_a.size() - 2) / 2); j >= 0; j--) { //向下调整算法 _AdjustDown(j); } } void Push(const T x)//插入元素 { _a.push_back(x); _AdjustUp(_a.size() - 1); } void Pop()//删除元素 { assert(_a.size() > 0); swap(_a[0], _a[_a.size() - 1]); _a.pop_back(); _AdjustDown(0); } size_t Size() { return _a.size(); } bool Empty() { return _a.empty(); } void print() { for (int i = 0; i < _a.size(); i++) { cout << _a[i] << " "; } cout << endl; } protected: //向下调整算法 void _AdjustDown(size_t parent) { size_t child = parent * 2 + 1; comer com; while (child < _a.size()) { //找出左右孩子中比较大的 if (child + 1 < _a.size() && com(_a[child + 1] , _a[child])) { child++; } //比较父亲和孩子的大小 if (com (_a[child],_a[parent])) { swap(_a[child], _a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //向上调整算法 void _AdjustUp(size_t child) { assert(child < _a.size()); int parent = (child - 1) / 2; comer com; while (child > 0) { //只需看父节点<根节点 if (com(_a[child], _a[parent])) { swap(_a[child], _a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } private: vector <T> _a; };
需要学习的也就是向上以及向下调整算法。
欢迎大家提出宝贵的意见。
测试用例如下:
void Test() { int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 }; Heap<int,Less<int> > hp1(a, sizeof(a) / sizeof(a[0])); hp1.print(); cout << hp1.Size() << endl; cout << hp1.Empty() << endl; hp1.Push(20); hp1.print(); cout << hp1.Size() << endl; cout << hp1.Empty() << endl; hp1.Pop(); hp1.print(); cout << hp1.Size() << endl; cout << hp1.Empty() << endl;
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。