纸上谈兵: 堆 (heap)

堆(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函数,测试相关的操作。

总结

堆,优先级

插入元素,删除最大优先级元素

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ImportSource

来自JVM的一封ClassFile介绍信

我是一个class文件。我的内部是由一个被叫做ClassFile的structure组成。 我在jvm中占有很重要的地位,你可去看看jvm规范中我占了多少篇幅...

38580
来自专栏架构说

redis-哈希表自动扩容

@(架构说)[redis] 为了回答上次遗留问题 哈希表如何扩容问题? 重点内容: 1 注释代码:最新版本 https://github.com...

65530
来自专栏Java帮帮-微信公众号-技术文章全总结

Java中的24种设计模式与7大原则

一、创建型模式 1、抽象工厂模式(Abstract factory pattern): 提供一个接口, 用于创建相关或依赖对象的家族, 而不需要指定具体类. 2...

37270
来自专栏瓜大三哥

Verilog代码设计风格

1.信号命名规则 信号命名规则在团队开发中占据着重要地位,统一、有序的命名能大幅减少设计人员之间的冗余工作,还可便于团队成员代码的查错和验证。比较著名的信号命名...

23270
来自专栏平凡文摘

JDK 10 的 109 项新特性

11720
来自专栏一名合格java开发的自我修养

提取jedis源码的一致性hash代码作为通用工具类

一致性Hash算法是来解决热点问题,如果虚拟节点设置过小热点问题仍旧存在。 关于一致性Hash算法的原理我就不说了,网上有很多人提供自己编写的一致性Hash算...

15330
来自专栏前端达人

用Async解决回调问题

第一次接触编程时,我们就知道了一块代码是从头执行到尾的。 这就是所谓的同步编程:每个操作完成之后,后面的才会继续。 对于不花计算机太多时间的操作,比如数字相加、...

13540
来自专栏java一日一条

Java 容器相关知识全面总结

Java实用类库提供了一套相当完整的容器来帮助我们解决很多具体问题。因为我本身是一名Android开发者,包括我在内很多安卓开发,最拿手的就是ListView(...

13410
来自专栏酷玩时刻

微信扫码支付(模式一)微信扫码支付(模式一)

官方文档地址:https://pay.weixin.qq.com/wiki/doc/api/native.php?chapter=6_4

24730
来自专栏老九学堂

2016计算机二级Java考试真题大放送,还不快收藏!

1、[单选题] 在软件开发中,需求分析阶段可以使用的工具是(  )。 A.N-S图 B.DFD图 C.PAD图 D.程序流程图 参考答案:B 参考解析:在软...

41340

扫码关注云+社区

领取腾讯云代金券