最大堆的JAVA实现

最大堆是一种数据结构，使用完全二叉树来实现，每一个节点都比它的左右孩子节点要大（有点类似于金字塔，数值最大的在塔顶，数值小的在塔底，高度越高，数值越大）

这种结构最适合做什么呢？它，最适合于在一坨数据中找最大值。为甚？大家想想，既然在任何时候塔顶的数都是最大的，这不就意味着我们在任何时候都可以直接抓取最大值了吗，完事了塔顶又是最大值，我们又一次拥有了抓取最大值的机会…如此循环反复，取之不尽用之不竭，子子孙孙无穷无尽也。

堆是怎么实现的呢？

堆的创建

一般来说，堆的物理数据结构是数组（毕竟堆使用了完全二叉树，数组的最经济最划算的选择，根据孩子找父母或是根据父母找孩子都异常简单与方便），数组的第一个元素被放弃使用，因为我们使用child / 2的公式找父母，使用parent * 2与parent * 2 + 1找左右孩子。

我们首先将所有元素存入数组中，之后从最后一个非叶子节点开始进行调整（如果最大那个孩子比它大，就将它与那个孩子交换，交换后也许它又比新孩子小，就又要调整…如此循环不断），直到调整至根节点。

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
// 堆的创建
private void create(List<Integer> data) {
    if (!this.data.isEmpty()) {
        this.data.clear();
    }

    // 舍弃第一个数组元素
    this.data.add(0);

    // 新元素全部加入数组
    this.data.addAll(data);

    int parent, child;
    // 从最后一个非叶子节点(size / 2)开始调整，直到根
    for (int i = (this.data.size() - 1) / 2; i >= 1; i--) {
        parent = i;

        // 不断地与大于parent的child交换，直到不可交换为止
        while (parent <= (this.data.size() - 1) / 2) {
            child = parent * 2;

            // 右孩子更大
            if (child + 1 <= (this.data.size() - 1) && this.data.get(child) < this.data.get(child + 1)) {
                child = child + 1;
            }

            // parent与child交换，并查看是否要继续调整
            if (this.data.get(parent) < this.data.get(child)) {
                swap(parent, child);
                parent = child;
            } else {
                // parent与child之间已经符合要求，无须交换
                break;
            }
        }

    }
}

从上面分析可知，平均复杂度是O(n)，最差情况是O(nLogn)

往堆中插入一个数据

由于堆使用了完全二叉树，往堆中插入一个数据时，最好插入到数组尾部（插到其它地方需要移动数组，效率会被拉低），之后将该数据与父母节点比较，并相应做交换，使其逐渐地上浮到相应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//  往堆中插入一个数据
private void insert(Integer element) {
    this.data.add(element);

    int parent, child = this.data.size() - 1;

    // 从最后一个非叶子节点(size / 2)开始调整，直到根
    for (int i = (this.data.size() - 1) / 2; i >= 1; ) {
        parent = i;
        if (this.data.get(parent) < this.data.get(child)) {
            swap(parent, child);
            child = parent;
            i = i / 2;
        }
        else {
            break;
        }
    }
}

时间复杂度是O(LogN)

删除堆中数组某个下标的数据

想要删除，直接将最后一个数据覆盖欲删除的数据，之后进行调整即可。

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
// 删除堆中数组某个下标的数据
private void delete(int index) {
    this.data.set(index, this.data.get(this.data.size() - 1));
    this.data.remove(this.data.size() - 1);

    int parent = index, child;

    for (; parent >= (this.data.size() - 1) / 2; ) {
        child = parent * 2;

        // 没有孩子
        if (child > this.data.size() - 1) {
            return;

            // 有左右两个孩子
        } else if (child < this.data.size() - 1) {
            // 右孩子更大
            if (this.data.get(child) < this.data.get(child + 1))
                child = child + 1;

            // 只有左孩子
        } else if (child == this.data.size() - 1) {

        }

        // 交换parent和child
        swap(parent, child);

        // 可能要继续下沉
        parent = child;
    }
}

时间复杂度是O(LogN)