堆排序、优先级队列以及相关复杂度分析

堆(heap)是一种特殊的数据结构,主要用途是排序,以及构造优先级队列。

什么是堆?

堆首先是一棵完全二叉树,结点从上到下、从左到右依次排列下来,中间没有空隙结点。完全二叉树有几个重要性质,下面的算法以及复杂度分析会用到:

  • 结点数量为 n 的完全二叉树的高度为:[log2n]+1
  • 第 i 层有 2i-1个结点;也就是每层结点数量是 q = 2 的等比数列;
  • 第 i 个结点的子结点编号是 2*i 和 2*i +1 ;

其次,堆有一个重要性质:每个结点的值都小于(或是大于)其子结点。如果是小于的话,那么树的根节点是最小元素,这样的堆是小顶堆;如果是大于的话,那么根结点是最大元素,这样的堆是大顶堆。下面均以小顶堆为例进行分析。

堆排序

给 n 个数,假设堆构造好了,那么树根便是最小元素。如果取走根部的最小元素,用最后一个元素替代,那么剩下的 1 ~ n-1个元素构成的堆,除了顶部之外其他部分均还是堆。所以对新的顶部元素进行调整,那么便会形成 n-1 个元素的堆,顶部又是最小元素。循环往复,那么进行 n-1 次取元素以及调整,n 个数的从小到大的排序便完成了。

现在来看下调整:只有顶部元素不符合最小值之外,其他部分均满足堆的结构。画个图很容易看出来,将顶部元素和子结点进行比较,将小的子结点升上去,大的父节点降下来,只需要进行 h(树的高度)次转换,便会形成新的堆。

所以如果不考虑最初建堆的过程,那么 n 个元素的堆排序,时间复杂度是 O(nlogn),这是显而易见的。

堆的初始化

如何将最初的 n 个元素形成一个小顶堆呢?有一种构造方法是:从 i = n/2 个元素开始,将 i 对应的子树调整成堆,然后调整 i-1,i-2,... 一直到第 1 个元素。为嘛是从 第 i = n/2 个元素起呢?因为 n/2 之后的元素都是叶子节点,本身就是符合堆的结构的。

  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "os"
  6. )
  7.  
  8. type Heap []int
  9.  
  10. func swap(a, b *int) {
  11.     *b, *a = *a, *b
  12. }
  13.  
  14. func (h Heap) adjust_down(i int) {
  15.     n := len(h) - 1 // length
  16.     for i <= n/2 {
  17.         var j = 2 * i
  18.         if j+1 <= n && h[j+1] < h[j] {
  19.             j++
  20.         }
  21.         if h[i] < h[j] {
  22.             break
  23.         }
  24.         swap(&h[i], &h[j])
  25.         i = j
  26.     }
  27. }
  28.  
  29. func (h Heap) sort() {
  30.     n := len(h) - 1               // length
  31.     for i := n / 2; i >= 1; i-- { // init
  32.         h.adjust_down(i)
  33.     }
  34.  
  35.     for i := 1; i < n; i++ { // swap & adjust
  36.         swap(&h[1], &h[n+1-i])
  37.         hh := h[0 : n-i+1]
  38.         hh.adjust_down(1)
  39.     }
  40. }
  41.  
  42. func main() {
  43.     var data []int = make([]int, 1, 100)
  44.     var item int
  45.     data[0] = 0
  46.     for {
  47.         _, err := fmt.Fscanf(os.Stdin, "%d", &item)
  48.         if err != nil {
  49.             break
  50.         }
  51.         data = append(data, item)
  52.     }
  53.  
  54.     var heap = Heap(data)
  55.  
  56.     heap.sort()
  57.     fmt.Println(heap)
  58. }

这是用 go 写的一个堆排序的列子,仅供参考。

此种方法将 n 个元素构造成一个堆的时间成本是 O(n)。简单证明如下:

假设有 2n-1 个元素,树的高度是 n,第 n 层全部是叶子结点,结点数是 2n-1,
初始化堆需要进行的交换次数:
x = 2n-1*0 + 2n-2*1 + 2n-3*2 + 2n-4*3 + ... + 1 * (n-1)
学过高中代数的人都知道:2x = ...
那么 x = 2x - x = 2n - n - 1 ,其中总结点数是:2n-1
so, 对于 n 个数初始化建堆的成本是 O(n) 。

优先级队列

优先级队列,首先是一个队列,其次队首是优先级最高(或是最低)的元素。队列因为会频繁的插入和删除,所以如果用普通的 array 或是 list 组织的话,每次遍历 O(n) 取优先级最高的元素,代价成本略大。

假设队列元素结构是一个堆,那么移除一个元素再调整,时间复杂度是 O(logn)。如果是插入元素,假设插入到队列的尾部,那么也是调整一个堆,不过和前面从上向下调整不一样,这里应该是从下向上调整,目测时间复杂度也是 O(logn)。

  1. func (h Heap) adjust_up(i int) {
  2.     for i > 1 {
  3.         if h[i/2] <= h[i] {
  4.             break
  5.         }
  6.         swap(&h[i], &h[i/2])
  7.         i = i / 2
  8.     }
  9. }

这是从下向上调整的代码。前提:除了最后一个元素之外,其他均满足堆的结构。

Tags: 

Article type: