堆是一种特殊的树结构,其经典的应用堆排序是一种原地的,时间复杂度是O(nlogn)的排序算法

堆的定义

  • 堆是一颗完全二叉树
  • 堆中每一个节点都必须大于等于(或小于等于)其子树中每一个节点的值
  • 堆中每一个节点都大于等于其子树中每一个节点的值的叫大顶堆,对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作小顶堆。

堆的构建

由于堆是完全二叉树,而使用数组存储完全二叉树是最节省内存的,因此我们使用数组来存储堆。 如图所示,用数组存储堆的例子:

堆的两种主要操作 往堆中插入数据删除堆顶元素

往堆中插入数据

往堆中插入数据后,会破坏堆的特性,因此需要堆化的过程。堆化分为两种,从下往上堆化从上往下堆化,插入数据的过程一般用 从下往上堆化

从下往上堆化
将数据插入数组末尾,然后和父节点比较,如果不符合大小关系则交换,以此类推,不停比较交换,直到父子节点满足大小关系。
堆化过程图:

代码实现:

type heap []int

func (h heap) Insert(data int) {
    if len(heap) == 0 {
        h = append(h, 0)
    }
    h = append(h, data)
    index = len(h) - 1

    for index/2 > 0 && h[index] > h[index/2] {
        h[index], h[index/2] = h[index/2], h[index]
        index = index/2
    }
}

删除堆顶元素

如果是大顶堆,删除堆顶元素后,我们需要从左右子节点选取大的节点填充父节点,那左右节点空出来的位子继续从其子节点选取。过程如下:

上图可知,虽然这种思路执行完成后,产生空的叶子节点,导致堆不符合完全二叉树的定义。为了解决这个问题,我们需要使用从上往下堆化的方法。

从上往下堆化
我们删除堆顶元素后,直接将堆中的最后一个节点删除放到堆顶,然后堆顶和其左右子节点比较大小,如果不符合大小关系,则交换,以此类推,直到父节点和子节点满足堆的定义。
堆化的过程图

代码实现:

type heap []int

func (h heap) RemoveMax() {
    if len(h) == 1 {
        return
    }
    h[1] = h[len(h)-1]
    h.heapify(1)
}

func (h heap) heapify(index int) {
    maxPos := index
    for {
        if 2*index <= len(h)-1 && h[index] < h[2*index] {
            maxPos = 2*index
        }
        if 2*index+1 <= len(h)-1 && h[index] < h[2*index+1] {
            maxPos = 2*index + 1
        }
        if maxPos == index {
            break
        }
        h[index], h[maxPos] = h[maxPos], h[index]
        index = maxPos
    }
}

如何基于堆实现排序?

我们借助与堆这种数据结构排序的方法叫做堆排序,堆排序的时间复杂度是 O(nlogn),且时间复杂度非常稳定,是原地排序算法。

要实现堆排序需要两个步骤:建堆排序

建堆

将一个数组建堆有两种方式,第一种是上面提到的插入数据使用的从下往上堆化;第二种是从上往下堆化,使用第二种思路时,我们需要从后往前扫描数组,找到一个非叶子节点,然后使用从上往下堆化的方法和子节点比较,以此类推,依此堆化,直到堆化到根节点。
堆化过程:

代码实现:

func BuildHeap(h []int, l int) {
    for i := l/2; i >= 1; i-- {
       heapify(h, l, i) 
    }
}

func heapify(h []int, l, index int) {
    maxPos := index
    for {
        if 2*index <= len(h)-1 && h[index] < h[2*index] {
            maxPos = 2*index
        }
        if 2*index+1 <= len(h)-1 && h[index] < h[2*index+1] {
            maxPos = 2*index + 1
        }
        if maxPos == index {
            break
        }
        h[index], h[maxPos] = h[maxPos], h[index]
        index = maxPos
    }
}

由代码可知,如果数组大小是 n,则我们需要从下标 n/2 开始到 1 的数据进行堆化。

排序

建堆结束后(大顶堆),我们将堆顶元素和最后一个元素交换,那最大元素就放在了下标为 n 的位置,这个过程类似与删除堆顶元素。交换后,将下标 1 到 n-1 的元素重新堆化。堆化完成后,再取堆顶元素,以此类推,直到最后堆中只剩下标为 1 的一个元素,排序工作就完成了。

代码实现:

func Sort(h []int) {
    BuildHeap(h, len(h) - 1)
    k := len(h) - 1
    for k > 1 {
       h[1], h[k] = h[k], h[1]
       k = k - 1
       heapify(h, k, 1)
    } 
}