堆的结构分析与应用
在二叉树中,我们用两种方法表示二叉树,一个是链表,一个是数组,但是数组比较适用于满二叉树或者完全二叉树。
创新互联公司是一家集网站建设,石阡企业网站建设,石阡品牌网站建设,网站定制,石阡网站建设报价,网络营销,网络优化,石阡网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
堆结构的二叉树存储有两种方法:
最大堆:每个父节点的都大于孩子节点。
最小堆:每个父节点的都小于孩子节点。
#include#include #include using namespace std; template class Heap { public: Heap()//无参类型的构造函数 {} Heap(T *a, size_t size)//有参类型的构造函数 { assert(a); for (size_t i = 0; i < size; i++) { _a.push_back(a[i]); } //建堆,用 向下调整 算法 //对于一个完全二叉树,其结点的父子关系与数组的下标的关系: //左子下标= 父结点下标*2+1 //右子下标=父结点下标*2+2 for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点(最后一个元素一定是非叶子结点的子节点) { _AdjustDown(j); } /* 在第一次写时定义了j为size_t类型,由于j不管怎么运算都是无符号类型所以 j>=0并没有起到限制的作用,导致了死循环 */ } public: void Push(const T &x)//在最后加入一个节点 { _a.push_back(x); _AdjustUp(_a.size() - 1);//向上调整,传入最后一个元素下标(调整x的位置) } void Pop()//把最大的删掉(根) { assert(!_a.empty()); swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换 _a.pop_back();//删掉最后一个节点 _AdjustDown(0);//向下调整 } void Print() { for (size_t i = 0; i < _a.size(); i++) { cout << _a[i]<<" "; } cout << endl; } size_t size() { return _a.size(); } bool empty() { return _a.empty(); } protected: void _AdjustDown(size_t parent)//时间复杂度O(log2(N)) { size_t child = parent * 2 + 1; //找到其左孩子 while (child < _a.size()) { 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; } } void _AdjustUp(size_t child)//时间复杂度O(log2(N)) { size_t parent = (child - 1) / 2; while (child > 0) { if (_a[child] > _a[parent]) { swap(_a[child], _a[parent]); child = parent; parent = (child - 1) / 2; } else break; } } private: vector _a; };
测试函数
void test() { int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 }; Heaph2(a, 10); h2.Push(3); h2.Push(4); h2.Print(); h2.Push(100); h2.Print(); h2.Pop(); h2.Print(); h2.Pop(); h2.Print(); } int main() { test(); getchar(); return 0; }
上面实现了最大堆,最小堆方法同最大堆,但是再在类中重新一遍则会使程序的可维护性降低,所以我们用仿函数来实现。
仿函数
仿函数就是使一个类使用看上去像一个函数,其实现就是类中实现一个operator().这个类就有了类似函数的行为。
struct
Free
{
void
operator()(
void
*ptr)
{
free
( ptr);
}
};
void
Testsharedptr()
{
int
*p1=(
int
*)
malloc
(
sizeof
(
int
)*10);
shared_ptr<
int
>sp1(p1,Free());
//在使用完后自动释放p1
}
用仿函数实现最大堆与最小堆
templatestruct Less { bool operator()(const T&left, const T&right) { return left < right; } }; template struct Greater { bool operator()(const T&left, const T&right) { return left>right; } }; template > class Heap { public: Heap()//无参类型的构造函数 {} Heap(T *a, size_t size)//有参类型的构造函数 { assert(a); for (size_t i = 0; i < size; i++) { _a.push_back(a[i]); } //建堆,用 向下调整 算法 //对于一个完全二叉树,其结点的父子关系与数组的下标的关系: //左子下标= 父结点下标*2+1 //右子下标=父结点下标*2+2 for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点(最后一个元素一定是非叶子结点的子节点) { _AdjustDown(j); } } public: void Push(const T &x)//在最后加入一个节点 { _a.push_back(x); _AdjustUp(_a.size() - 1);//向上调整,传入最后一个元素下标(调整x的位置) } void Pop()//把最大的删掉(根) { assert(!_a.empty()); swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换 _a.pop_back();//删掉最后一个节点 _AdjustDown(0);//向下调整 } void Print() { for (size_t i = 0; i < _a.size(); i++) { cout << _a[i]<<" "; } cout << endl; } size_t size() { return _a.size(); } bool empty() { return _a.empty(); } protected: void _AdjustDown(size_t parent)//时间复杂度O(log2(N)) { size_t child = parent * 2 + 1; //找到其左孩子 compare 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)//时间复杂度O(log2(N)) { size_t parent = (child - 1) / 2; compare 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 _a; };
这样就实现了最大堆与最小堆,通过仿函数,程序的可维护性好于在类中写一个最大堆写法和最小堆写法。
测试
void test1() { int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 }; int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 }; Heap> h2(a, 10);//最小堆 h2.Push(3); h2.Push(4); h2.Print(); h2.Push(100); h2.Print(); h2.Pop(); h2.Print(); h2.Pop(); h2.Print(); Heap h3(b);//最大堆 h3.Push(3); h3.Push(4); h3.Print(); h3.Push(100); h3.Print(); h3.Pop(); h3.Print(); h3.Pop(); h3.Print(); }
堆的应用:
1.堆排序
分析:由于在大堆或者小堆排完后,只能保证每个小树为大堆或者小堆,故还需要进行排序才能使数组元素完全依次排列。
所以我们先用大堆排列后,使堆顶元素为大元素,再依次将堆顶元素和未交换的最后一个元素交换,交换完成后再将除了大的元素之外的元素进行交换
/****************************** 堆排序 尽建立一个大堆,每次把堆顶的元素和最后一个还未交换的元素交换 */ void AdjustDown(int *a, int parent, int size) { int child = parent * 2 + 1; while (child < size) { if (a[child] a[parent]) { swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; } else break; } } void HeapSort(int *a, int n) { assert(a); for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(a,i,n);//大堆向下调整 } for (int i = 0; i < n; i++) { swap(a[n - 1 - i],a[0]); AdjustDown(a, 0, n - 1 - i); } }
2.求N个元素中前K个最大的数
分析:建立一个小堆存放前K个元素,小堆的堆顶元素为前K个中最小的值,剩下N-K个数中依次和堆顶元素相比较,若大于堆顶元素,入堆,每入堆一个元素再小堆排序一次,使堆顶元素总为这K个元素的最小值;若小于堆顶元素,则继续下一个数比较。当N-K个元素全比较完,堆中这K个元素就是最大的前K个数。
/* 从N个数中找到K个最大的数 建立一个小堆,大小为K,每次从第N-K的数据中取出一个和堆顶元素比较 */ const int N = 1000000; const int K = 100; void AdjustDown(int *a, int parent, int size) { int child = parent * 2 + 1; while (childa[child + 1]) { child++; } if (a[child] < a[parent]) { swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; } else break; } } void GetTopK(int *a) { assert(K < N); int top[100]; for (size_t i = 0; i < 100; i++) { top[i] = a[i]; } //建一个小堆,向下调整 for (int i = (K - 2) / 2; i>=0; i--) { AdjustDown(top, i, K); } //从剩下的N-K的数据中拿数据和堆顶元素比较,若小于堆顶元素,则入堆 for (size_t j = K; j < N ; j++) { if (a[j]
分享名称:堆的结构分析与应用
当前URL:http://scyanting.com/article/jsgjhe.html