二叉堆

2025-05-04

Algorithm

无标签

文章目录

结构#

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。

由堆性质，树根存的是最大值（getmax 操作就解决了）。

节点结构#

对于任意节点 $i$
节点的父节点： $\frac{i-1}{2}$
节点的左子节点： $2i+1$
节点的右子节点： $2i+2$

过程#

堆的核心操作有两个：

堆化上浮：如果节点比父节点大,则与父节点交换,重复此过程直到根节点。操作结束后,能确保节点满足堆性质。

堆化下沉：在节点的子节点中,找到一个最大的,与该节点交换,重复此过程到底层。操作结束后,能确保节点满足堆性质。

辅助函数”#

1
    int GetParent(int i) => (i - 1) / 2;
2
    int GetLeftChild(int i) => (i * 2) + 1;
3
    int GetRightChild(int i) => (i * 2) + 2;
4
    int GetFirstLeaf(int n) => n / 2;

堆化下沉#

1
// n 是堆的大小，i 是当前节点的索引
2
template<typename T>
3
void ShiftDown(T arr[], int n, int i) {
4
    while (true)
5
    {
6
        int largest = i;
7
        int left = GetLeftChild(i);
8
        int right = GetRightChild(i);
9
        if (left < n && arr[left] > arr[largest]) {
10
            largest = left;
11
        }
12
        if (right < n && arr[right] > arr[largest]) {
13
            largest = right;
14
        }
15
        if (largest == i)
16
            break;
17

18
        Swap(arr[i], arr[largest]);
19
        i = largest;
20
    }
21
}

堆化上浮#

1
template<typename T>
2
void ShiftDown(T arr[], int n, int i) {
3
    while (i > 0)
4
    {
5
        int parent = GetParent(i);
6
        if (arr[parent] >= arr[i])
7
            break;
8

9
        Swap(arr[parent], arr[i]);
10
        i = parent;
11
    }
12
}

建堆#

上浮实现堆有序

1
template<typename T>
2
void Heapify(T arr[], int n) {
3
    for (int i = 0; i < n; i++)
4
    {
5
        ShiftUp(arr, n, i);
6
    }
7
}

对于第 $k$ 层的结点，向上调整的复杂度为 $O(k)$ 而不是 $O(\log n)$ 。

总复杂度： $\log 1 + \log 2 + \cdots + \log n = \Theta(n \log n)$ 。

上浮操作的复杂度是高于下沉的,所以一般采用下沉实现堆有序。

下沉实现堆有序

1
template<typename T>
2
void Heapify(T arr[], int n) {
3
    for (int i = GetFirstLeaf(n) - 1; i >= 0; i--)
4
    {
5
        ShiftDown(arr, n, i);
6
    }
7
}