算法笔记 -- 堆和堆排序
2021-11-29 19:19:37 # algorithm # algorithm # 计算机基础

之前一直对堆这个数据结构和堆排序不太了解,今天正好在leetcode上写题的时候又复习了一遍,在这里记录一下堆和堆排序。

堆

堆是一种特殊的二叉树，在一些语言中也称为优先队列。满足以下的性质：

  • 堆是一棵完全二叉树，除了最后一层，其他层的节点都是满的，最后一层从左部开始连续；

  • 堆的每一个节点的值都大于（大根堆）或小于（小根堆）它的左右子树的值；

    img

    堆不像\(BST\)一样严格，只要求某个节点的值比它的左子树右子树都更大或更小就可以，所以同一组数据，可以构建出多种形态的堆。

    img

堆大部分情况下都用数组来表示

img

如上图所示，比较容易地可以发现规律，对于数组中索引为\(i\)地根节点，它的左子树索引为\(2 \times i + 1\)，右子树的索引为\(2\times i + 2\)。

对于一个索引为\(i\)的节点，它的父节点索引为\(floor((i-1)/2)\)，向下取整。

堆的操作

堆的操作主要包括插入和删除。由于插入和删除后都可能不再满足堆的性质，所以在插入或删除之后都要对堆进行调整，这个过程也称为\(heapify\)。

堆化

堆化\(heapify\)包括从下往上的上浮过程和从上往下的下降过程。

上浮过程是当前元素不断向上和父节点比较大小：

对于大根堆，当前元素比父节点大，交换，让大的节点上去，对于小根堆，当前元素比父节点小，交换，让小的节点上去。

img

下沉过程是当前元素不断向下比较和两个孩子的大小关系：

对于大根堆，当前元素和孩子中较大的比较，比子节点小就交换，让小的下去，对于小根堆，当前元素和孩子中较小的比较，比子节点大就交换，让大的节点下去。

img

插入

因为要满足完全二叉树的条件，所以在数组的末尾插入元素，再进行堆化。

img

让新插入的结点和父节点比较大小，如果新插入的结点大于父节点，则交换，一直重复到满足堆的条件。

img

删除

堆顶元素存储的就是堆中数据最大的或最小的，删除了堆顶元素之后，可以把最后一个元素移到根节点的位置，这样就可以满足完全二叉树的性质，再进行堆化。

img

最后一个节点放到堆顶，在子节点中找出较大(大顶堆)的那个对比。小于子节点时，互换两个节点，并且重复进行这个过程。

建堆

建立堆有两种方式，一种是从前往后，一种是从后往前。

从前往后依次处理数组，数据插入到堆中时，不借助另一个数组，直接在原数组上操作，采用从下往上的堆化，直到最后一个元素处理完成。这样处理的话，除了第一个节点不需要堆化，其他都需要堆化，对\(n-1\)个节点进行了堆化。

从后往前处理数组，使用从上往下堆化，直到第一个元素处理完成。对于完全二叉树来说，下标\(n/2+1\)到\(n\)的节点都是叶子节点，没有子树，所以可以直接从\(n/2\)开始。

复杂度分析

堆化的过程就是顺着节点所在的路径开始交换的，所以堆化的时间复杂度和树的高度成正比，所以为\(O(logn)\)。

插入和删除的时间复杂度也主要取决于堆化，所以时间复杂度为\(O(logn)\)。

建堆的过程中，由于叶子节点不需要堆化，所以堆化的节点从倒数第二层开始，每个节点堆化的过程中，需要比较和交换的节点个数是和高度成正比的。

img

所以建堆的时间复杂度为\(O(n)\)。

堆排序

堆排序是建立在一个堆的基础上的，数组的第一个元素就是堆顶，也就是最大或最小的那个元素，我们可以利用删除堆顶的思路来进行堆排序。

排序过程中需要对\(n\)个元素进行堆化，堆化的时间复杂度为\(O(logn)\)，所以排序的时间复杂度为\(O(nlogn)\)。

若是对大顶堆进行堆排序，则会得到一个升序数组，因为每次最大的元素都往后面移动，小顶堆排序得到降序数组。

堆排序不需要开辟额外空间，需要交换元素时的一个临时变量，所以空间复杂度为\(O(1)\)。

堆的应用

优先队列

普通的队列的出队顺序取决于入队顺序，优先队列的出队顺序取决于元素的优先级，可以理解为优先队列就是一个排序后的队列。堆是实现优先队列最直接的方式。因为堆和优先队列十分相似。

例如在实现定时器时，如果使用普通的队列，就需要不断轮询时间，扫描一趟任务列表，看看是否有任务到达设定的执行时间，到达了就开始执行这个任务。但是这样实现会导致很多躺扫描其实是不必要的，而且每次轮询如果任务列表比较大，耗时也会比较长。

如果使用优先队列，可以根据任务设定的执行时间，将这些任务存储在一个优先队列中，堆顶存储的是最先执行的任务，拿队首的任务的执行时间点，与当前时间点相减，就可以得到下一次执行任务的时间，这样也省去了这段时间的轮询。这段时间间隔过去后，取出堆顶，再重新计算堆顶即可。

TopK

在一堆数据里找到前K大的数。

因为取前3大的元素是降序排序，所以可以使用小顶堆来求解。

例如求数组\([4,5,3,7,1,8]\)中的前3大元素。

Setp1:取前3大元素是降序，所以选择小堆顶。取出前三个数组[4，5，3]，建小顶堆，得到 [3，4，5]；

Setp2:遍历数组到元素7，比堆顶元素3大，将3移除，将7放入堆中，堆化后，小顶堆变为 [4，5，7]

Setp3:接着遍历数组到元素1，比堆顶元素4小，不处理

Setp4:接着遍历数组到元素8，比堆顶元素4大，将4移除，将8放入堆中，堆化后，小顶堆变为 [5，8，7]，此时遍历结束，顶堆中的元素就是前 3 大元素

求动态数据集合中的中位数

维护两个堆，一个大顶堆，一个小顶堆。

n 个数据，n 是偶数。前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中，保证小顶堆中的数据都大于大顶堆中的数据，此时的中位数就是大根堆的堆顶元素和小根堆的堆顶元素相加除以2。

n 是奇数。大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据，此时的中位数就是大根堆的堆顶。

新添加一个数据的时候，如果新加入的数据小于等于大顶堆的堆顶元素，将这个新数据插入到大顶堆；否则，将这个新数据插入到小顶堆。

两个堆中的数据个数不符合约定数量时,数量少的堆将堆顶元素移动到另一个堆，直至平衡。

堆的代码实现（Java）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
public class Heap {
    private int[] heap;
    private int heapSize;

    /**
     * 初始化堆
     *
     * @param capacity 堆的容量
     */
    public Heap(int capacity) {
        this.heapSize = 0;
        this.heap = new int[capacity + 1];
        Arrays.fill(heap, 0);
    }

    /**
     * 判断堆是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 判断堆是否为满
     *
     * @return
     */
    public boolean isFull() {
        return this.heapSize == this.heap.length;
    }

    /**
     * 返回i节点下标的父节点下标,数组下标从0开始
     *
     * @param i
     * @return
     */
    private int parent(int i) {
        return (i - 1) / 2;
    }

    /**
     * 返回堆顶元素
     *
     * @return
     */
    public int heapTop() {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空");
        }
        return heap[0];
    }

    /**
     * 添加元素
     *
     * @param val
     */
    public void insert(int val) {
        if (isFull()) {
            throw new NoSuchElementException("堆已满");
        }
        heap[heapSize++] = val;
        // 向上调整(维护堆结构)
        heapifyUp(heapSize - 1);
    }

    /**
     * 删除堆中下标为i的元素
     *
     * @param i
     * @return
     */
    public int remove(int i) {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空");
        }
        int ret = heap[i];
        // 用末尾的元素覆盖要删除的元素
        heap[i] = heap[heapSize - 1];
        heapSize--;
        heapifyDown(i);
        return ret;
    }

    /**
     * 向上维护堆
     *
     * @param i
     */
    private void heapifyUp(int i) {
        int insertVal = heap[i];
        while (i > 0 && insertVal > heap[parent(i)]) {
            heap[i] = heap[parent(i)];
            i = parent(i);
        }
        heap[i] = insertVal;
    }

    /**
     * 返回左右子下标中较大的下标
     *
     * @param i
     * @return
     */
    private int maxChild(int i) {
        int leftChild = (2 * i + 1);
        int rightChild = (2 * i + 2);
        return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
    }

    /**
     * 向下交换进行维护
     *
     * @param i
     */
    private void heapifyDown(int i) {
        int child;
        // 保存要交换前i下标对应的值
        int temp = heap[i];
        // 当数组未越界，维护堆（如果左右子下标中较大的子下标的值大于父下标，则它们进行交换。)
        while ((2 * i + 1) < heapSize) {
            child = maxChild(i);
            if (temp >= heap[child]) {
                break;
            }
            heap[i] = heap[child];
            i = child;
        }
        heap[i] = temp;
    }
}
上一页
2021-11-29 19:19:37 # algorithm # algorithm # 计算机基础
下一页