首页 > 代码库 > 二叉堆的实现
二叉堆的实现
/* ** 二叉堆的实现 ** 堆最重要的性质是儿子的值大于等于父亲的值,除此之外, ** 树的节点是按照从上到下,从左到右的顺序紧凑排列的。 ** ** 插入:首先在末尾插入,然后不断向上提升直到没有大小颠倒为止。 ** 删除:首先把堆的最后一个元素复制到根节点并且删除最后一个 ** 节点。然后不断向下交换直到没有大小颠倒为止。在向下交换过程 ** 中,如果有两个儿子,那么选择数值较小的儿子进行交换。 */ #include <stdio.h> #include <string.h> #define maxn 1000 int heap[maxn], sz = 1; // 1为根节点 void push(int x) { int i = sz++; while(i > 1) { int p = i >> 1; // 父亲节点 if(heap[p] <= x) break; // 不再颠倒 heap[i] = heap[p]; // 把父亲节点放下,自己提上去 i = p; } heap[i] = x; } int top() { // ...需要先判断非空 return heap[1]; } void pop() { // 出队,同时返回队首元素 int ret = heap[1]; int x = heap[--sz]; // 要提到根的数值 int i = 1; while(i * 2 < sz) { int a = i << 1; b = i << 1 | 1; 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; }
二叉堆的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。