纸上谈兵: 堆 (heap)
- 时间:
- 浏览:0
- 来源:十分时时彩_十分时时彩下注平台_十分时时彩游戏平台
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!
堆(heap)又被为优先队列(priority queue)。尽管名为优先队列,但堆并也有队列。回忆一下,在队列中,大伙儿能都可不能否了进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中,大伙儿也有按照元素进入队列的先后顺序取出元素的,很久按照元素的优先级取出元素。
这就好像候机的以前,无论谁先到达候机厅,总是头等舱的乘客先登机,很久是商务舱的乘客,最后是经济舱的乘客。每个乘客也有头等舱、商务舱、经济舱两种个键值(key)中的四个 。头等舱->商务舱->经济舱依次享有从高到低的优先级。
再比如,封建社会的等级制度,也是四个 堆。在这人 堆中,国王、贵族、骑士和农民是从高到低的优先级。
封建等级
Linux内核中的调度器(scheduler)会按照各个多线程 的优先级来安排CPU执行哪四个 多线程 。计算机中通常有多个多线程 ,每个多线程 有不同的优先级(该优先级的计算会综合多个因素,比如多线程 所时需耗费的时间,多线程 将会等待歌曲的时间,用户的优先级,用户设定的多线程 优先程度等等)。内核会找到优先级最高的多线程 ,并执行。将会有优先级更高的多线程 被提交,没人调度器会转而安排该多线程 运行。优先级比较低的多线程 则会等待歌曲。“堆”是实现调度器的理想数据型态。
(Linux中能都可不能否了使用nice命令来影响多线程 的优先级)
堆的实现
堆的四个 经典的实现是删改二叉树(complete binary tree)。很久实现的堆成为二叉堆(binary heap)。
删改二叉树是增加了限定条件的二叉树。假设四个 二叉树的深层为n。为了满足删改二叉树的要求,该二叉树的前n-1层时需填满,第n层也时需按照从左到右的顺序被填满,比如下图:
为了实现堆的操作,大伙儿额外增加四个 要求: 任意节点的优先级不小于它的子节点。将会在上图中,设定小的元素值享有高的优先级,没人上图就符合该要求。
这人似于“叠罗汉”。叠罗汉最重要的许多,很久让体重大的参与者站在最下面,让体重小的参与者站在上面 (体重小,优先级高)。为了让“堆”稳固,大伙儿每次只允许最上面的参与者退出堆。也很久,每次取出的优先级最高的元素。
四个 “叠罗汉”堆
我将会在排序算法简介及其C实现中实际使用了堆。堆的主要操作是插入和删除最小元素(元素值两种为优先级键值,小元素享有高优先级)。在插入将会删除操作以前,大伙儿时需保持该实现应有的性质: 1. 删改二叉树 2. 每个节点值都小于或等于它的子节点。
在插入操作的以前,会破坏上述堆的性质,很多有时需进行名为percolate_up的操作,以进行恢复。新插入的节点new上放删改二叉树最后的位置,再和父节点比较。将会new节点比父节点小,没人交换两者。交换以前,继续和新的父节点比较…… 直到new节点不比父节点小,将会new节点成为根节点。很久得到的树,就恢复了堆的性质。
大伙儿插入节点2:
插入
删除操作都可不能否了删除根节点。根节点删除后,大伙儿会有四个 子树,大伙儿时需基于它们重构堆。进行percolate_down的操作: 让最后四个 节点last成为新的节点,从而构成四个 新的二叉树。再将last节点不断的和子节点比较。将会last节点比四个 子节点中小的那四个 大,则和该子节点交换。直到last节点不大于任一子节点都小,将会last节点成为叶节点。
删除根节点1。如图:
删除根节点
下面是代码。与大伙儿在二叉搜索树中使用表不同,大伙儿这里使用数组来表示删改二叉树。数组下标为0的元素不让于储存节点,而用于记录删改二叉树中元素的总数。
/* By Vamei
Use an big array to implement heap
DECLARE: int heap[MAXSIZE] in calling function
heap[0] : total nodes in the heap
for a node i, its children are i*2 and i*2+1 (if exists)
its parent is i/2 */
void insert(int new, int heap[])
{
int childIdx, parentIdx;
heap[0] = heap[0] + 1;
heap[heap[0]] = new;
/* recover heap property */
percolate_up(heap);
}
static void percolate_up(int heap[]) {
int lightIdx, parentIdx;
lightIdx = heap[0];
parentIdx = lightIdx/2;
/* lightIdx is root? && swap? */
while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
/* swap */
swap(heap + lightIdx, heap + parentIdx);
lightIdx = parentIdx;
parentIdx = lightIdx/2;
}
}
int delete_min(int heap[])
{
int min;
if (heap[0] < 1) {
/* delete element from an empty heap */
printf("Error: delete_min from an empty heap.");
exit(1);
}
/* delete root
move the last leaf to the root */
min = heap[1];
swap(heap + 1, heap + heap[0]);
heap[0] -= 1;
/* recover heap property */
percolate_down(heap);
return min;
}
static void percolate_down(int heap[]) {
int heavyIdx;
int childIdx1, childIdx2, minIdx;
int sign; /* state variable, 1: swap; 0: no swap */
heavyIdx = 1;
do {
sign = 0;
childIdx1 = heavyIdx*2;
childIdx2 = childIdx1 + 1;
if (childIdx1 > heap[0]) {
/* both children are null */
break;
}
else if (childIdx2 > heap[0]) {
/* right children is null */
minIdx = childIdx1;
}
else {
minIdx = (heap[childIdx1] < heap[childIdx2]) ?
childIdx1 : childIdx2;
}
if (heap[heavyIdx] > heap[minIdx]) {
/* swap with child */
swap(heap + heavyIdx, heap + minIdx);
heavyIdx = minIdx;
sign = 1;
}
} while(sign == 1);
}
要我尝试一下构建买车人的main函数,测试相关的操作。
总结
堆,优先级
插入元素,删除最大优先级元素
欢迎继续阅读“纸上谈兵: 算法与数据型态”系列。