堆 (数据结构)

维基百科,自由的百科全书
跳转至: 导航搜索

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

逻辑定义[编辑]

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

性质[编辑]

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

  • 任意节点小于它的所有后裔,最小元在堆的根上(堆序性)。
  • 堆总是一棵完全树

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

支持的基本操作[编辑]

堆支持以下的基本操作:

  • build:建立一个空堆;
  • insert:向堆中插入一个新元素;
  • update:将新元素提升使其符合堆的性质;
  • get:获取当前堆顶元素的值;
  • delete:删除堆顶元素;
  • heapify:使删除堆顶元素的堆再次成为堆。

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

例程[编辑]

为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。[1]

void Insert( ElementType X, PriorityQueue H )
{
    int i;
 
    if( IsFull(H) )
    {
        printf( "Queue is full.\n" );
        return;
    }
 
    for( i = ++H->Size; H->Element[i/2] > X; i /= 2 )
        H->Elements[i] = H->Elements[i/2];
    H->Elements[i] = X;
}

以上是插入到一个二叉堆的过程。

DeleteMin,删除最小元,即二叉树的根或父节点。删除该节点元素后,队列最后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤

ElementType
DeleteMin( PriorityQueue H )
{
    int i, Child;
    ElementType MinElement, LastElement;
 
    if( IsEmpty( H ) )
    {
        printf( "Queue is empty.\n" );
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];
 
    for( i = 1; i*2 <= H->Size; i = Child )
    {
        /* Find smaller child. */
        Child = i*2;
        if( Child != H->Size && H->Elements[Child+1]
                             <  H->Elements[Child] )
            Child++;
 
        /* Perlocate one level. */
        if( LastElement > H->Elements[Child] )
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

应用[编辑]

堆排序[编辑]

堆(通常是二叉堆)常用于排序。这种算法称作堆排序

事件模拟[编辑]

主要运用堆的排序以选择优先。

参考[编辑]

  1. ^ 1.0 1.1 《数据结构与算法分析》 Mark Allen Weiss(美)第六章,优先队列(堆)。

参见[编辑]