数据结构——堆

1 堆的基本概念

● 堆的定义
○ 堆是一类特殊的数据结构的统称，堆通常可以被看成一颗完全二叉树的数组对象
● 堆的特性
○ 堆是完全二叉树，除了树的最后一层节点不需要是满的，其他的每一层从左到右都是满的，如果最后一层节点不是满的，那么要求左满右不满

○ 通常使用数组来实现
■ 如果一个节点的位置为k，则它的父节点的位置为[k/2]，而它的两个子节点的位置分别为2k和2k+1.这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k] 向上一层，就令k/2，向下一层就令k等于2k或2k+1

○ 每个节点都大于等于它的两个节点，这里要注意堆中仅仅规定了每个节点大于等于它的两个子节点，但这两个子节点的顺序并没有做规定，跟二叉查找树是有区别的

2 代码实现

2.1 insert 插入方法的实现

● 将要插入的值添加到数组的末尾
● 将插入的值使用上浮算法调整到合适的位置

2.2delMax删除最大元素方法的实现

● 将根节点和索引最后一个节点进行交换，交换后将最后一个索引的值进行删除
● 将根节点使用下沉算法调整到合适的位置

2.3 代码

import com.sun.org.apache.xpath.internal.operations.String;

public class Heap<T extends Comparable<T>> {
   
    // 存储堆中的元素
    private T[] items;
    // 记录堆中元素的个数
    private int n;

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

    // 判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
   
        return items[i].compareTo(items[j]) < 0;
    }

    // 交换堆中索引i处的元素是否小于索引j处的元素
    private void exch(int i, int j) {
   
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    // 往堆中插入一个元素
    public void insert(T t) {
   
        items[++n] = t;
        swim(n);
    }

    // 删除堆中最大的元素，并返回最大的元素
    p
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