众所周知,堆是一种很好用的数据结构,是基于完全二叉树的。
1 //堆的数组实现 2 const int Maxsize = 10000; 3 int len = 0; //记录当前size 4 int heap[Maxsize+1]; 5 6 //当然也可以用vector实现 7 vector <int> Heap; 8 9 //每一次插入新的数据,都要和它的父节点比一比(判别依据是根据本来是大根堆||小根堆) 10 //以小根堆举例,插入的复杂度为O(logn) 11 void Up(int k){ 12 while(k > 1 && heap[k] < heap[k/2]){ 13 swap(heap[k], heap[k/2]); 14 k /= 2; 15 } 16 } 17 18 void Insert(int x){ 19 heap[++len] = x; 20 Up(len); 21 } 22 23 //堆最常用的功能就是维护min||max 24 //以小根堆为例,我们常常会求得最小的数字,然后让它出堆; 25 //这时候我们就要从堆中删除堆顶元素。 26 //由于这时除了堆顶为空,它的左右子树堆仍然满足堆结构。 27 //为了操作简单,我们将堆尾元素放到堆顶,然后再将其"逐 步 下 移" 28 void Down(int k){ 29 while(k + k <= len){ 30 int j = k + k; 31 if (j + 1 <= len && heap[j + 1] < heap[j]){ 32 j++; 33 } 34 if (heap[k] <= heap[j]){ 35 break; 36 } 37 swap(heap[k],heap[j]); 38 k = j; 39 } 40 } 41 42 void Pop(){ 43 swap(heap[1],heap[len]); 44 len--; 45 Down(1); 46 } 47 48 //删除堆中任意一个元素 49 void Delete(int p){ 50 if (p == len){ 51 heap[len] = 0; //这句其实可以不写 52 len--; 53 return; 54 } 55 int x = heap[p]; 56 int y = heap[len]; 57 swap(heap[p],heap[len]); 58 len--; 59 if (y < x){ 60 Up(p); 61 } 62 else{ 63 Down(p); 64 } 65 }
当然,对于我这种Blue_Dog(bushi),可以采用方便的STL
STL里的堆的缺点就是没办法clear,也不知道为什么。
1 //STL 2 //大根堆: 3 priority_queue<int> q1; 4 priority_queue<int, vector<int>,less<int>> q2; 5 6 //小根堆: 7 priority_queue<int, vector<int>,greater<int>> q3; 8 9 //基本操作:empty size top push pop...(没有clear)