欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列/堆的基础

程序员文章站 2024-02-13 14:34:16
...

优先队列(堆)的定义和性质

定义:
优先队列: 特殊的“队列”,取出元素的顺序是按照它的优先级大小,而不是元素进入队列的先后顺序。

使用堆来实现优先队列。
性质:

  1. 结构性:用数组表示的完全二叉树。
  2. 有序性:任一结点是其子树所有结点的最大值(或最小值)。
    最大堆:maxHeap,也叫大顶堆
    最小堆:minHeap,也叫小顶堆
  3. 从根结点到任意结点的路径上,都是有序的。

基础操作

下面以大顶堆为例进行说明

1.初始化

  • 堆可以用数组实现
  • 数组的第0个元素可以作为“哨兵”,不存储实际使用的值,用来简化堆中的一些操作。比如存一个后面结点永远比它小的值(MAX_VALUE),这样可以方便后面的插入操作。

优先队列/堆的基础

2. 插入

  1. 在数组后面插入新值
  2. 从新值从下往上进行调整,只要它比父结点大,父结点就往下移动;否则停止,将该值放到对应的位置

优先队列/堆的基础

3.删除堆顶元素(删除最大值)

  1. 记录堆顶元素。
  2. 将堆的最后一个元素放到堆顶。然后进行堆的调整。
  3. 从根结点开始,取它的左右子节点的最大值,看子节点是否比它大,如果子节点更大,将子节点往上移动,然后再看子节点的左右子节点,直到叶子节点或者左右子节点比该值小。

优先队列/堆的基础

4.堆的构建

方式一: 循环插入 O(N*logN),将元素一个一个插入初始为空的堆中。
方式二:首先将N个元素顺序存入数组,先满足完全二叉树的性质;然后再从n/2的位置开始调整堆,使之符合有序性。每次调整都是 左右两个子树原本都是堆,然后将根结点进行调整。类似于删除最大元素之后的调整。时间复杂度O(n)。

/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X;
 
    X = H->Data[p]; /* 取出根结点存放的值 */
    for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}
 
void BuildHeap( MaxHeap H )
{ /* 调整H->Data[]中的元素,使满足最大堆的有序性  */
  /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
    int i;
    /* 从最后一个结点的父节点开始,到根结点1 */
    for( i = H->Size/2; i>0; i-- )
        PercDown( H, i );
}

优先队列/堆的基础