【代码】堆

发表于 更新于 阅读次数：

前言

堆的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
package com;

public class Heap<T extends Comparable<T>> {

    private T[] items;
    private int heapLength;

    public Heap(int capacity) {
        this.items = (T[]) new Comparable[capacity+1];
        this.heapLength = 0;
    }

    /**
     * 插入一个元素
     * @param t
     */
    public void insert(T t) {
        items[++heapLength] = t;
        swim(heapLength);
    }

    /**
     * 使用上浮算法
     * 使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void swim(int k) {
        // 通过循环，不断地比较当前结点的值和其父结点的值
        while (k > 1) {
            // 如果父结点的值小于当前结点的值，交换位置
            if (items[k/2].compareTo(items[k])<0) {
                T temp = items[k/2];
                items[k/2] = items[k];
                items[k] = temp;
            }
            k = k/2;
        }
    }

    /**
     * 删除最大的元素，并返回这个元素
     * @return
     */
    public T deleteMax() {
        T max = items[1];
        // 交换索引1处的元素和最大索引的元素，让完全二叉树中最右侧的元素变为临时根节点
        T temp = items[1];
        items[1] = items[heapLength];
        items[heapLength] = temp;
        // 最大索引处的元素删除掉
        items[heapLength] = null;
        // 元素个数自减
        heapLength--;
        // 通过下沉，调整堆，让堆重新有序
        sink(1);
        return max;
    }

    /**
     * 使用下浮算法
     * 使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void sink(int k) {
        // 通过循环不断的对比当前结点和其较大的子结点
        while (2*k <= heapLength) {

            int max;
            // 如果有右子结点，就比较两个子结点的值
            if (2*k+1 <= heapLength) {
                // 找到当前结点的两个子结点中较大的一个结点的索引
                max = items[2*k].compareTo(items[2*k+1])>0?2*k:2*k+1;
            }
            // 如果没有右子结点
            else {
                // 直接把当前结点的左子结点的索引赋值给最大值
                max = 2*k;
            }
            // 如果当前结点的值小于当前结点的较大子结点的值，则交换位置
            if (items[k].compareTo(items[max])<0) {
                T temp = items[k];
                items[k] = items[max];
                items[max] = temp;
                // 变换当前结点的索引
                k = max;
            }
            // 如果当前结点的值大于当前结点的较大子结点的值，则直接退出循环
            else {
                break;
            }
        }
    }

}

完成

参考文献

哔哩哔哩——黑马程序员