堆和堆排序

2023/05/12

Tags: Algorithm

堆

堆的本质是树，用数组表示的完全二叉树；

定义

一棵深度为k且有 2^k - 1 个结点的二叉树称为满二叉树。

根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 2^(i-1) 个结点 (i≥1) 。

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

参考： https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232

性质

arr：[2 3 4 52 2 2 1]
idx： 0 1 2 3  4 5 6

i 下标和元素之间的映射关系：

大根堆

完全二叉树里，每一个子树的最大值是根节点；

小根堆

完全二叉树里，每一个子树的最小值是根节点；

堆排序

定义堆

// maxHeap 定义一个大根堆
type maxHeap struct {
    Data  []int
    Count int
}

func NewMaxHeap(size int) *maxHeap {
    return &maxHeap{
        Data:  make([]int, size),
        Count: 0,
    }
}

插入数据

插入数据时，是往数组最后增加元素，由于需要保证大根堆的性质，如果新加入的元素比父节点大，则跟父节点交换位置，以此类推，一直到根节点，这个交换流程完成后，新元素插入就完成了。

父节点下标跟当前下标index的关系：父节点 = (i-1)/2

// insert 向堆中插入元素
func (heap *maxHeap) Insert(val int) {
heap.Data[heap.Count] = val
    heap.Count++
    // heap.shiftUp(heap.Count)
    heap.shiftUp1(heap.Count - 1) // 最后一个元素的下标
}

// shiftUp 向堆中插入元素时，叶子节点可能需要向上移动
func (heap *maxHeap) shiftUp1(index int) {
    // 父节点 = (i-1)/2
    for index > 0 && heap.Data[index] > heap.Data[(index-1)/2] {
        heap.Data[index], heap.Data[(index-1)/2] = heap.Data[(index-1)/2], heap.Data[index]
        index = (index - 1) / 2
    }
    fmt.Printf("shiftUp heap %v \n", heap)
}

// shiftUp 向堆中插入元素时，叶子节点可能需要向上移动
func (heap *maxHeap) shiftUp(count int) {
    for count > 1 && heap.Data[count-1] > heap.Data[(count/2)-1] {
        heap.Data[count-1], heap.Data[(count/2)-1] = heap.Data[(count/2)-1], heap.Data[count-1]
        count = (count / 2)
    }
    fmt.Printf("shiftUp heap %v \n", heap)
}

移除数据

移除数据，就是移除根节点，同时把最后一个元素放到根节点，然后跟子节点比较，此时，大根堆需要找到左右子节点中，较大的一个元素，跟父节点进行互换，以此类推，直到比较完最后一个节点，同时 count-1；

// ExtraMax 提取大根堆的最大值，也就是根节点，大根堆整体性质不变
func (heap *maxHeap) ExtraMax() int {
    heap.Count--
    result := heap.Data[0]
    heap.Data[0], heap.Data[heap.Count] = heap.Data[heap.Count], heap.Data[0]
    heap.shiftDown(0)
    return result
}

// shiftDown 移除堆中元素，节点向下移动
func (heap *maxHeap) shiftDown(index int) {
    for index <= heap.Count-1 {
        i := heap.getMaxChildNode(index)
        if i == -1 {
            break
        }
        if heap.Data[index] < heap.Data[i] {
            heap.Data[index], heap.Data[i] = heap.Data[i], heap.Data[index]
        }
        index = i
    }
}

// getMaxChildNode 获取最大子节点下标，如果没有子节点，return -1
func (heap *maxHeap) getMaxChildNode(index int) int {
    if index <= heap.Count-1 {
        if index*2+2 > heap.Count-1 {
            // 当右节点下标越界时
            if index*2+1 <= heap.Count-1 {
                // 如果左下标没有越界，则返回左节点下标
                return index*2 + 1
            }
        } else {
            // 当右节点下标没有越界时，此时左下标一定没有越界
            if heap.Data[index*2+1] >= heap.Data[index*2+2] {
                return index*2 + 1
            } else {
                return index*2 + 2
            }
        }
    }
    // 没有子节点时，返回-1
    return -1
}

堆初始化

堆的内部实际是一个数组，数组可以通过下标表示为树形结构，堆初始化可以把数组转化为大根堆或者小根堆，这里需要借助完全二叉树的性质：

最后一个非叶子节点是：(n-1)/2 (n 是数组大小)

// MaxHeapipy 最大堆初始化
func MaxHeapipy(arr []int) *maxHeap {
    mh := NewMaxHeap(len(arr))
    mh.Data = arr
    mh.Count = len(arr)
    // 堆是一棵完全二叉树，最后一个非叶子节点是：(n-1)/2，n 是数组大小
    // 基于这个性质，可以依次对每一个非叶子节点进行 shiftDown，相当于每一个子树都完成 shiftDown，
    // 最后完成根节点的 shiftDown
    // shiftDown 之后，依然保持大根堆的性质
    for i := (mh.Count - 1) / 2; i >= 0; i-- {
        mh.shiftDown(i)
    }
    return mh
}

堆排序扩展

已知一个几乎有序的数组，几乎有序是指，如果把数组排好序的话，每个元素移动的距离不可以超过k，并且k相对于数组来说比较小。请选择一个合适的算法针对这个数据进行排序。

假设k=6，准备一个小根堆，遍历数组，把前7个元素构建一个小根堆，则0位置是数组的最小值（因为排好序之后，每个元素移动距离不会超过k），把小根堆的根节点弹出，放到数组的0位置，然后依次把7个元素之后的数据插入到小根堆，弹出根节点的数据，弹出的数据一次有序。