堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。
堆的常用方法
构建优先队列
支持堆排序
快速找出一个集合中的最小值(或者最大值)
堆属性
堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。
在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。
堆并不能取代二叉搜索树 ,它们之间有相似之处也有一些不同。
节点的顺序。在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。
内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组,且不使用指针。
平衡。二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O ( log n ) O(\log n) O ( log n ) 。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O ( log n ) O(\log n) O ( log n ) 的性能。
搜索。在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。
最大堆代码实现(代码来源 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <bitset> #include <string> #include <cmath> #include <sstream> using namespace std ; typedef long long ll;const double pi = acos (-1.0 );const int eps = 1e-10 ;const int mod = 1e9 + 7 ;const int INF = 0x3f3f3f3f ;const int maxn = 1005 ;const int MaxData = INF;const int MaxSize = maxn;typedef int ElementType;typedef struct HeapStruct *MaxHeap ;MaxHeap Create (int MaxSize) ; bool IsFull (MaxHeap H) ;void Insert (MaxHeap H, ElementType item) ;bool IsEmpty (MaxHeap H) ;ElementType DeleteMax (MaxHeap H) ; struct HeapStruct { ElementType *Elements; int Size; int Capacity; }; class __MaxHeap { public: MaxHeap ele; MaxHeap Create (int MaxSize) { MaxHeap H = (MaxHeap)malloc (sizeof (struct HeapStruct)); H->Elements = (ElementType*)malloc ((MaxSize + 1 ) * sizeof (ElementType)); H->Size = 0 ; H->Capacity = MaxSize; H->Elements[0 ] = MaxData; return H; } void Insert (MaxHeap H, ElementType item) { int i; if (IsFull(H)) { printf ("最大堆已满\n" ); return ; } i = ++H->Size; for (; H->Elements[i / 2 ] < item; i /= 2 ) H->Elements[i] = H->Elements[i / 2 ]; H->Elements[i] = item; } ElementType DeleteMax (MaxHeap H) { int Parent, Child; ElementType MaxItem, temp; if (IsEmpty(H)) { printf ("最大堆空\n" ); return -1 ; } MaxItem = H->Elements[1 ]; temp = H->Elements[H->Size--]; for (Parent = 1 ; Parent * 2 <= H->Size; Parent = Child) { Child = Parent * 2 ; if ((Child != H->Size) && (H->Elements[Child] < H->Elements[Child + 1 ])) Child++; if (temp >= H->Elements[Child]) break ; else H->Elements[Parent] = H->Elements[Child]; } H->Elements[Parent] = temp; return MaxItem; } bool IsFull (MaxHeap H) { return (H->Size == H->Capacity); } bool IsEmpty (MaxHeap H) { return (H->Size == 0 ); } void Print (MaxHeap H) { int co = 2 ; for (int i = 1 ; i <= H->Size; i++) { i > co - 1 ?puts ("" ),co <<= 1 :i; printf ("%d " , H->Elements[i]); } puts ("\n" ); return ; } }; int main () { __MaxHeap H; H.ele = H.Create(MaxSize); H.Insert(H.ele, 5 ); H.Insert(H.ele, 4 ); H.Insert(H.ele, 10 ); H.Insert(H.ele, 8 ); H.Insert(H.ele, 7 ); H.Insert(H.ele, 9 ); H.Insert(H.ele, 6 ); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); H.DeleteMax(H.ele); H.Print(H.ele); return 0 ; }
stl优先队列+最小堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> using namespace std ; #define MAX_N 10000 int heap[MAX_N],sz = 0 ;void push (int x) { int i = sz++; while (i > 0 ) { int p = (i - 1 ) / 2 ; if (heap[p] <= x) break ; heap[i] = heap[p]; i = p; } heap[i] = x; } int pop () { int ret = heap[0 ]; int x = heap[--sz]; int i = 0 ; while (i * 2 + 1 < sz) { int a = i * 2 + 1 ,b = i * 2 + 2 ; if (b < sz && heap[b] < heap[a] ) a = b; if (heap[a] >= x) break ; heap[i] = heap[a]; i = a; } heap[i] = x; return ret; } int main () { push(10 ); push(1 ); push(2 ); cout <<pop()<<endl ; cout <<heap[0 ]<<endl ; priority_queue <int > q; q.push(10 ); q.push(1 ); q.push(2 ); cout <<q.top()<<endl ; q.pop(); cout <<q.top()<<endl ; return 0 ; }