云莉的技术专题

堆 Heap、二叉堆 Binary Heap

2020-03-29  本文已影响0人  云莉6

堆 Heap

在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题而设计的一种数据结构。

二叉堆是堆(优先队列 priority queue)的一种常见且简单的实现;但并不是最优的实现。

不同实现的比较:https://en.wikipedia.org/wiki/Heap_(data_structure)

性质

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均为该数据结构的这种实现。这种数据结构具有以下性质

将根节点最大的堆叫最大堆或大根堆,根节点最小的堆叫最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

二叉堆实现细节

  1. 二叉堆一般都通过“数组”来实现

  2. 假设“第一个元素”在数组中的索引为 0 的话,则父节点和子节点的位置关系如下:

    1. 根节点(顶堆元素)是:a[0]

    2. 索引为 i 的左孩子的索引是 (2*i + 1)

    3. 索引为 i 的右孩子的索引是 (2*i + 2)

    4. 索引为 i 的父节点的索引是 floor((i -1) / 2);

支持的基本操作

操作 描述 时间复杂度
build 创建一个空堆 O(n)
insert 向堆中插入一个新元素 O(log n)
update 将新元素提升使其其符合堆的性质
get 获取当前堆顶元素的值 O(1)
delete 删除堆顶元素 O(log n)
heapify 使删除堆顶元素的堆再次成为堆

某些堆实现还支持其他的一些操作,如斐波那契堆支持检查一个堆中是否存在某个元素。

大顶堆常见操作

insert 插入操作(HeapifyUp)

Delete Max 删除堆顶操作(HeapifyDown)

Find Max

上一篇 下一篇

猜你喜欢

热点阅读