堆

堆的性质

  • 堆是一个完全二叉树；
  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

堆顶元素大于子节点的称作大顶堆，堆顶元素小于子节点的堆称作小顶堆

堆的存储

因为堆是一个完全二叉树，比较适合使用顺序结构的数组来存储数据

堆的实现

以小顶堆为例，数据使用顺序结构存储。

定义：

//Heap 堆的定义
type Heap struct {
	data []int
}

//Insert param val
func (h *Heap) Insert(val int) {
}

//Delete param val
func (h *Heap) Remove(val int) {
}

辅助方法

  • 计算父节点的索引
func parentIdxOf(currentIdx int) int {
    if currentIdx <= 0 {
        return -1
    }
    if currentIdx&1 == 1 {
        return (currentIdx - 1) >> 1
    }
    return currentIdx>>1 - 1
}
  • 自顶向下调整
func siftDown(index int, data []int) {
    //调整堆
    idx, size := index, len(data)
    for {
        leftIdx := idx<<1 + 1
        rightIdx := leftIdx + 1
        if leftIdx >= size {
            //没有子节点，可以直接返回
            return
        } else if rightIdx >= size {
            //只有左节点
            if data[leftIdx] < data[idx] {
                data[leftIdx], data[idx] = data[idx], data[leftIdx]
            }
            return
        } else {
            //min(left, right), compare if swap then continue else break
            if data[leftIdx] < data[rightIdx] && data[idx] > data[leftIdx] {
                data[leftIdx], data[idx] = data[idx], data[leftIdx]
                idx = leftIdx
            } else if data[rightIdx] < data[leftIdx] && data[idx] > data[rightIdx] {
                data[rightIdx], data[idx] = data[idx], data[rightIdx]
                idx = rightIdx
            } else {
                return
            }
        }
    }
}
  • 自底向上调整
func siftUp(index int, data int) {
    for idx := index; idx > 0; {
        //找到父节点，如果需要调整，交换之后，从父节点再向上调整，直到根节点
        parentIdx := parentIdxOf(idx)
        if data[parentIdx] < data[idx] {
            data[parentIdx], data[idx] = data[idx], data[parentIdx]
            idx = parentIdx
            continue
        }
        break
    }
}

堆的操作

1.insert

对于插入操作，在插入数据之后，我们需要对数组调整，以维持堆的性质，调整的过程叫做堆化（heapify）。

insert过程

  • 数组扩容（如果有必要）
  • 将元素放置到 数组的第 size（数组元素的个数）位置处
  • 调整元素位置

调整的过程通常分为两种：自顶下先和自底向上

自底向上：将新插入的元素和其父节点比较，如果元素值大于父节点，交换两个节点的值，再从其父节点开始交换，否则调整完成

//Insert param val
func (h *Heap) Insert(val int) {
    h.data = append(h.data, val)
    //将元素append 到数组的最后，再从最后一个元素开始向上调整
    siftUp(len(h.data) - 1)
}

2.remove
堆相对于二叉搜索树而言，只能保证堆顶（根节点是最大/小）的元素，如果需要查找某个元素是否在堆中，最坏的情况可能是$O(n)$,因为每个子树可能都需要查找，堆的删除一般都是针对堆顶元素的删除而言的。

//定义一个查找元素的方法
func find(val, start, size int, data []int) int {
    if data[start] == val {
        return start
    }
    idx, leftIdx := -1,  start<<1 + 1
    if leftIdx >= size || data[leftIdx] > val {
        return idx
    }
    //查找左子树
    idx = find(val, leftIdx, size, data)
    if idx >= 0 {
        return idx
    }
    rightIdx := leftIdx + 1
    if rightIdx >= size || data[rightIdx] > val {
        return idx
    }
    //查找右子树
    return find(val, rightIdx, size, data)
}

func (h *Heap) find(val int) int {
    size := len(h.data)
    if size == 0 {
        return -1
    }
    return find(val, 0, size, h.data)
}

java的 PriorityQueue对于查找的实现，就是从队列的底层数组中线性查找（这种查找可能比使用数的性质递归查找性能更高，对数组的访问是线性的，更符合程序的局部性原则）

private int indexOf(Object o) {
    if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

删除堆顶元素之后，还需要调整堆的结构，以保证堆的基本性质。

堆化过程

  • 将数组的最后一个元素替换查找的元素
  • 从当前位置开始，比较节点和子节点元素的大小，不满足堆的性质则进行交换，否则结束
  • 交换之后，从被交换的子节点开始，再进行比较，直到结束
//Delete heap
func (h *Heap) Delete() {
    size := len(h.data)
    if size == 0 {
        return
    }
    //将堆顶元素替换成最后一个元素
    h.data[0] = h.data[size-1]
    h.data = h.data[:size-1]
    //自顶向下调整堆顶元素
    siftDown(0, h.data)
}

时间复杂度分析

对于一个已存在的堆而言，假设元素个数是n，根据完全二叉树的性质，树的高度 $h = [log_2(n + 1)]$，插入数据时，节点最多有 h个节点，也就是最多需要比较 h次，因此插入的时间复杂度是 $O(log_2n)$

删除类似新增，从根节点到叶子节点，最多需要比较的次数也和树的高度相关，时间复杂度也是 $O(log_2n)$

数组堆化

假设有n个元素的数组，构成完全二叉树的高度是 $H = [log_2(n + 1)]$，对于第 h层，元素个数最多$2 ^ {h-1}$

方案1：

参照堆的插入，插入的前提是已存在一个堆（或者是空堆），假设当前索引 i，加上这个元素之后，堆的高度是h，索引前面的数组元素满足堆的性质，对于第 i 个元素，依次找到节点的父节点索引，判断是否需要交换，直到不需要交换或者节点是堆的顶点（索引是0），最多需要比较的次数是 $h-1$，第h层的所有元素需要比较的次数是 $(h - 1) * 2 ^ {h-1}$
H层的所有节点（加上是一个满二叉树）的比较次数是

$$\sum_{h=1}^{H}(h-1) * 2 ^ {h-1} = \sum_{h=1}^{H-1}(h) * 2 ^ h = (H - 2)*2^H + 2$$

化简之后等于 $([log_2{(n+1)}] - 2)*(2^{[log_2{(n+1)}]}) + 2$，因此算法的时间复杂度为 $O(nlog_2n)$

func heapify(data []int) {
    for i := range data {
        if i == 0 {
            continue
        }
        idx, pIdx := i, parentIdxOf(i)
        for pIdx >= 0 && adatarr[idx] < data[pIdx] {
            data[idx], data[pIdx] = data[pIdx], data[idx]
            idx, pIdx = pIdx, parentIdxOf(pIdx)
        }
    }
}

方案2：

自底向上，加上当前节点的子树都满足堆的性质，比较和调整当前节点和子树的元素，使以当前节点为根的树也满足堆的性质，直到树的根节点

假设当前索引是i, 在完全二叉树中的层是h，其子树的高度是 $H - h$，最多需要比较和调整的次数就是子树的高度，第h层的节点的全部比较次数是

$$\sum_{h=1}^{H-1}2 ^ {h-1} * (H - h) = H * \sum_{h=1}^{H-1}2^{h-1} - (\sum_{h=1}^{H-1}h*2^{h}) / 2$$

化简之后等于 $H * (2^{H - 1}) - H - ((H - 2) * 2 ^ H + 2) / 2 = 2^H - H - 1$，近似等于 $n - log_2n$，算法时间复杂度是 $O(n)$

func heapify(data []int) {
    size := len(data)
    if size > 1 {
        for idx := parentIdxOf(size - 1); idx >= 0; idx-- {
            siftDown(idx)
        }
    }
}

堆的使用场景

  • 堆排序，特别是对于海量数据的排序，如 top k问题，取海量数据的最大(小)的前k个数据
  • 实现优先级队列，java中的 PriorityQueue

附：数学公式的证明

  1. $\sum_{i=1}^{n}i * 2 ^ i = (n - 1)*2^{n+1} + 2$

$$证明：
S_n = \sum_{i=1}^ni * 2 ^ i\\\\
S_n = 1*2^1+2*2^2+3*2^3+...+n*2^n\\\\
2S_n = 1*2^2+2*2^3+3*2^4+...+n*2^{n+1}\\\\
S_n - 2S_n = 2^1+2^2+2^3+...+2^n-n*2^{n+1}\\\\
S_n = n*2^{n+1} - \sum_{i=1}^n2^i = n * 2^{n+1} - 2^{n+1} + 2 = (n - 1)*2^{n+1} + 2$$

TAG:数据结构/heap