引例：在搜索算法实现中，会遇到这样一个问题——我们并不希望按照入队的先后顺序出队，而是希望每次出队的都是队列中最大或最小的元素。

而要实现这样的方式，我们可以假设一种队列，取出元素的顺序以大小为准，我们往往将这样的队列称之为优先队列。

优先队列（Priority Queue）：特殊的“队列”，依照元素的优先权（关键字）大小取出数据，而不是元素进入队列的先后顺序。

选择合适的数据结构

既然已经有了这样一个设想，那我们应该采用何种方式来实现呢？

使用数组或者链表

我们首先会想到以前学过的基本内容，以数组，链表等方式来储存，为了方便判断各种储存方法的优劣，我们将几种方法的时间复杂度进行比较。

  • 普通数组

    插入：我们只需要将普通数组的尾部即可    —— 时间复杂度 O(1)

    删除：需要从数组中查找最大或最小的元素，进行一次遍历即可    —— 时间复杂度为 O(n)

  • 链表

    插入：元素总是插在链表的头部(头插法)    —— 时间复杂度 O(1)

    删除：同样需要遍历查找查找最大或最小元素    —— 时间复杂度 O(1)

  • 有序数组：即在插入时就按照一定顺序插入

    插入：找到合适位置 —— 时间复杂度 O(n) 或者 O(log n) 【二分查找】         移动元素并插入    —— 时间复杂度 O(n)

    删除：删去最后一个元素    —— 时间复杂度 O(n)

  • 有序链表：同有序数组插入时按照一定顺序插入

    插入：找到合适的位置    —— 时间复杂度为 O(n)   插入元素    —— 时间复杂度 O(1)

    删除：删除首元素或者最后的元素    —— 时间复杂度为 O(1)

我们发现，以上四种实现方式的时间复杂度基本都是 O(n) ，那么可不可以找得到一种数据结构，来降低其时间复杂度呢？

那么就只有树了！我们可以用二叉树来实现，因为平衡二叉树的删除与插入时间复杂度都是与树高有关，时间复杂度是 logN 的。

二叉搜索树

二叉搜索树可以很好地进行插入与删除操作，删除时只需要将最左或者最右元素删除。但如果删除元素变多之后，可能会出现树”一边倒“ 的情况，这时会使时间复杂度变大，不再为 O(logN)，所以使用二叉搜索树也不很合适。

完全二叉树

将最大值或者最小值置于根结点处，用完全二叉树来存储，在删除之时就可以避免树出现“一边倒”的情况 。

而这种数据结构，便被称作堆。堆在中文维基百科中的定义如下：

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。

实现堆

堆的两个特性 ：

结构性：用数组表示的完全二叉树； 

有序性：任一结点的关键字是其子树所有结点的最大值(或最小值) 

  • “最大堆(MaxHeap)”,也称“大顶堆”：最大值 
  • “最小堆(MinHeap)”,也称“小顶堆” ：最小值

堆的抽象数据类型描述

类型名称：最大堆（MaxHeap） 

数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值

操作集：最大堆H 属于 MaxHeap ，元素item 属于 ElementType

主要操作有： 

  • MaxHeap Create( int MaxSize )： 创建一个空的最大堆。 

  • Boolean IsFull( MaxHeap H )：判断最大堆H是否已满。

  • Insert( MaxHeap H, ElementType item )：将元素 item 插入最大堆 H。 

  • Boolean IsEmpty( MaxHeap H )：判断最大堆H是否为空。

  • ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高优先级)。

堆的构建

首先应该了解怎样创建一个空的最大堆，但在这之前，我们首先应该设计出合适的结构体来表示堆 ：

代码

1
2
3
4
5
6
typedef struct HeapStruct *MaxHeap ;
struct HeapStruct{
	ElementType  *Elements ;	// 存储堆元素的数组
	int  Size ;					// 堆当前的元素个数
	int  Capacity ;				// 堆的最大容量
};

堆中元素的插入

插入分两步：

  1. 将元素插入到数组中元素之后，也就是末位，使之符合完全二叉树的结构
  2. 调整元素位置，使之成为堆

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void Insert ( MaxHeap H, ElementType item ){
	int  i ;
	if ( isFull(H) ){
		printf("最大堆已满");
        return ;
	}
    // i 指向插入后 堆中最后一个元素的位置
	i = ++H->Size ;   
	for  ( ; H->Elements[i] > H->Elements[i/2] ; i/=2 )
        // 向下过滤节点
		H->Elements[i] = H->Elements[i/2] ;     
	H->Elements[i] = item ; // 将item插入
}

理解：

  • 代码的主要部分为 for 循环及之后，for 循环在于将新插入至末尾的结点与其父节点进行比较，如新插入节点更大，则将其父节点与其交换位置，即可变为堆。

注意：

  • 交换位置之时，在循环中直接将父节点覆盖子节点，而最后再将新需要插入的结点直接插入到相应位置之中，可以提高效率。
  • 循环之时，如果在堆中不设哨兵，在循环之时还应进行判断，使其循环替换元素之时不能出堆

最大堆的删除

最大堆的删除操作也就是删除掉堆中的最大元素（即树根），并将之返回出去

删除之后堆中会少一个元素，因此我们的思路是：

  • 在删除操作进行之时首先将树根元素复制并返回，之后直接将数组最后一个元素将树根元素直接覆盖。
  • 然后就是将元素顺序再重新调整为一个堆。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ElementType  DeleteMax( MaxHeap H ){
	int  parent, child ;
    ElementType  MaxItem, temp ;
    if ( IsEmpty(H) ){
        printf("最大堆已空") ；
            return ;
    }
    MaxItem = H->Elements[1] ;    // 取出根节点的最大值
    temp = H->Elements[H->Size--] ;     // 将最后一个元素赋给temp
    for ( parent = 1 ; parent*2 <= H->Size ; parent = child ){
        child = parent * 2 ;
        if ( (child != H->Size) &&
            (H->Elements[child] < H->Elements[child+1]) )
            child++ ;   // 使 child 指向左右结点中较大者
        if ( temp >= H->Elements[child] )   break ;
        else  // 将 temp 元素移动到下一层
            H->Elements[parent] = H->Elements[child] ;
    }
    H->Elements[parent] = temp ;
    return MaxItem ;
}

理解：代码之中重点就在于重新调整元素，也就是 for 循环中内容——从根节点开始，依次与最大子结点比较，如果小于就与其交换位置，直至调整好为止。

注：for 循环的前一个if是用来调整 child 的，使 child 指向子结点中最大结点，之后就是调整结点元素的过程