数据结构-堆和堆的Java实现

定义

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。

常见的堆有二叉堆、斐波那契堆等。

堆的定义：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)

堆是一颗完全二叉树，在这棵树中，所有父节点都满足大于等于其子节点的堆叫大根堆，所有父节点都满足小于等于其子节点的堆叫小根堆。
堆虽然是一颗树，但是通常存放在一个数组中，父节点和孩子节点的父子关系通过数组下标来确定。如下图的小根堆及存储它的数组：

从图中，我们可以很容易总结出，通过一个节点在数组中的索引怎么计算出它的父节点及左右孩子节点的索引？下面直接给出对应的Java代码：

 public int left(int i) {
        return (i + 1) * 2 - 1;
    }

    public int right(int i) {
        return (i + 1) * 2;
    }

    public int parent(int i) {
        // i为根结点
        if (i == 0) {
            return -1;
        }
        return (i - 1) / 2;
    }

Java算法

计算一个节点的父节点和左右孩子节点的索引对大根堆和小根堆都是一样的。要构建一个堆，除了知道怎么计算一个节点的父节点和孩子节点的索引外，我们还需要两个算法，即保持堆的性质和建堆。
我们将看到建堆的方法对大根堆和小根堆也是一样的。接下来看看“保持堆的性质”是个什么意思？
保持堆的性质，对大根堆和小根堆很相似，但不完全一样，所以得分开说。

大根堆

对大根堆来说是，已经存在两个大根堆，现在要把一个元素作为这两个大根堆根的父节点，构成一个新的堆，但是这个堆的根结点可能不满足大根堆的性质，也就是说，它可能比它的孩子节点小，所以需要对它进行操作，操作的方式就是，我们从这个节点和它的孩子节点中选出最大的，如果最大的节点是这个节点本身，堆就已经满足大根堆性质了，否则，将这个节点与最大节点交换，交换后该节点在新的位置上也可能违背大根堆性质，所以需要递归的进行，直至这个节点比孩子节点都大或者是子节点为止（这个过程也叫做元素下降，因为元素从根结点开始一步一步往下移）。下图是算法导论中给出大根堆保持堆的性质的伪代码：

对应的Java代码如下：

 public void heapify(T[] a, int i, int heapLength) {
        int l = left(i);
        int r = right(i);
        int largest = -1;
        /**
         * 下面两个if条件句用来找到三个元素中的最大元素的位置largest； 
         * l < heapLength说明l在数组内，i非叶子结点；
         */
        if (l < heapLength && a[i].compareTo(a[l]) < 0) {
            largest = l;
        } else {
            largest = i;
        }
        // r < heapLength说明r在数组内
        if (r < heapLength && a[largest].compareTo(a[r]) < 0) {
            largest = r;
        }
        // 如果i处元素不是最大的，就把i处的元素与最大处元素交换，交换会使元素下降
        if (i != largest) {
            T temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            // 交换元素后，以a[i]为根的树可能不在满足大根堆性质，于是递归调用该方法
            heapify(a, largest, heapLength);
        }
    }

小根堆

对小根堆，保持堆的性质，过程是，已经存在两个小根堆，现在要把一个元素作为这两个堆的根，作为新的小根堆，但是这个元素可能会违背小根堆的性质，所以需要将它下降，也就是说，不断将它与它和孩子节点中的最小节点交换，直到它是它和它孩子节点中最小的或者是叶子节点为止。对应的Java代码如下：

    public void heapify(T[] a, int i, int heapLength) {
        int l = left(i);
        int r = right(i);
        int smallest = -1;
        /**
         * 下面两个if条件句用来找到三个元素中的最小元素的位置smallest； 
         * s < heapLength说明l在数组内，i非叶子结点；
         */
        if (l < heapLength && a[i].compareTo(a[l]) > 0) {
            smallest = l;
        } else {
            smallest = i;
        }
        // r < heapLength说明r在数组内
        if (r < heapLength && a[smallest].compareTo(a[r]) > 0) {
            smallest = r;
        }
        // 如果i处元素不是最小的，就把i处的元素与最小处元素交换，交换会使元素下降
        if (i != smallest) {
            T temp = a[i];
            a[i] = a[smallest];
            a[smallest] = temp;
            // 交换元素后，以a[i]为根的树可能不在满足大根堆性质，于是递归调用该方法
            heapify(a, smallest, heapLength);
        }
    }

创建堆

有了上面的这些准备工作，我们终于可以建堆了。正如前面所说，建堆的过程对大根堆和小根堆是一样的。我们可以把单个元素看作大根堆或者小根堆。假设数组中最后一个堆元素的下标为i，则数组中从0下标开始，最后一个有孩子节点的元素就是j=parent(i)。于是，我们从j到0，对一个元素都调用heapify方法，堆就建好了。下图是算法导论给出的伪代码：

对应的Java代码如下：

    public  void buildHeap(T[] a, int heapLength) {
        // 从后往前看，lengthParent - 1处的元素是第一个有孩子节点的节点
        int lengthParent = parent(heapLength - 1);
        // 最初，parent(length)之后的所有元素都是叶子结点；
        // 因为大于length/2处元素的孩子节点如果存在，那么
        // 它们的数组下标值必定大于length，这与事实不符；
        // 在数组中，孩子元素必定在父亲元素的后面，从后往前
        // 对元素调用maxHeapify，保证了元素的孩子都是
        // 大根堆
        for(int i = lengthParent; i >= 0; i--){
            heapify(a, i, heapLength);
        }
    }

关于堆的用途，可能大家最熟悉堆排序了，除此之外，我们可以用堆构建优先级队列，因为我们可以在常数时间内获得堆中（优先级）最大或者最小的元素，这对于优先级队列来说是很重要的。