Heap and HashHeap

Heap

(英语:Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

逻辑定义

n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆:
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

顾名思义,堆的实现常常借助PriorityQueue。

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

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

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

HashHeap

在Java的PriorityQueue中,有remove这一个函数,可以删除指定的元素。此时的时间复杂度为O(n),因为在删除之前得先遍历一遍数组,找到该元素。

但是如果对这个操作的调用比较频繁,那么我们就可以对这个函数进行改进,即用一个Hash Table存储每个元素的数组的下标,这样,删除元素时,我们不用遍历数组来找到该元素的位置,直接删除即可,时间复杂度为O(logn)。

应用见

http://www.lintcode.com/en/problem/building-outline/

上一篇:Robocopy


下一篇:Unable to find vcvarsall.bat解决方法