此文待重构

简介

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（英语：min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（英语：max heap）。在堆中最顶端的那一个节点，称作根节点（英语：root node），根节点本身没有母节点（英语：parent node）。

堆始于 J._W._J._Williams 在 1964 年发表的堆排序（英语：heap sort），当时他提出了二叉堆树作为此算法的数据结构。堆在戴克斯特拉算法（英语：Dijkstra’s algorithm）中亦为重要的关键。

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

特点

二叉堆是一颗完全二叉树
堆中某个节点的值总是不大于(不小于)其父节点的值(最大堆或最小堆)

最大堆

实现步骤

本章我们将用数组存储一个最大堆，我们先来了解一下数组索引和堆直接的关系，下面两图分别从索引1开始和索引0开始的关系：

区别只是公式变换一下，但为了不浪费数组单元，我们从索引0开始实现代码。

代码实现

import com.wk.chapter01.array.DynamicGenericsArray;

public class MaxHeap<E extends Comparable<E>> {
    //使用第一章实现的动态泛型数组
    private DynamicGenericsArray<E> arrayheap;

    /**
     * 堆容量为数组容量
     *
     * @param capacity
     */
    public MaxHeap(int capacity) {
        this.arrayheap = new DynamicGenericsArray<>(capacity);
    }

    /**
     * 默认容量为10
     */
    public MaxHeap() {
        this.arrayheap = new DynamicGenericsArray<>();
    }

    //返回元素个数
    public int size() {
        return arrayheap.size();
    }

    //堆是否为空
    public boolean isEmpty() {
        return arrayheap.isEmpty();
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的父节点的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't hava parent");
        }
        return (index - 1) / 2;
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }
}

此处我们用到了第一章的动态泛型数组，且在其中添加了一个方法，用于交换两个索引的数据，该方法代码：

//交换i索引和j索引的数据
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("i or j isn't current index");
        }
        E temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

增加元素到堆中

 // 向堆中添加元素
 public void add(E e) {
     arrayheap.addLast(e);
     // 上浮该元素
     siftUp(arrayheap.size() - 1);
 }

// 在堆中上浮元素
 private void siftUp(int k) {
     // 如果该索引大于0且其父索引的元素小于该索引的元素，交换位置，并将父索引赋给该索引
     while (k > 0 && arrayheap.get(parent(k)).compareTo(arrayheap.get(k)) < 0) {
         arrayheap.swap(k, parent(k));
         k = parent(k);
     }
 }

当我们向堆中增加元素时，把其添加到最后，之后和其父节点对比，若其大于父节点元素，则违反最大堆的定义，需要交换位置，之后将父索引值赋给当前索引，继续循环。该操作类似上浮，直到其小于父节点元素停止该循环，过程如下图：

取出堆中的元素

//看堆中的最大元素
    public E findMax() {
        if (arrayheap.size() == 0) {
            throw new IllegalArgumentException("heap is empty");
        }
        return arrayheap.get(0);
    }

    //取出堆中最大元素
    public E extractMax() {
        E ret = findMax();
        arrayheap.swap(0, arrayheap.size() - 1);
        arrayheap.removeLast();
        siftDown(0);
        return ret;
    }

   //在堆中下沉元素
    private void siftDown(int k) {
        //当左孩子索引小于元素个数（说明其没有越界）
        while (leftChild(k) < arrayheap.size()) {
            //先定义i，它的索引等于左孩子
            int i = leftChild(k);
            //从定义可知右孩子索引比左孩子大1，判断一下右孩子索引是否越界
            //然后我们先比较一下右孩子的值是否大于左孩子，如果成立则将右孩子索引赋值给i
            if (i + 1 < arrayheap.size() && arrayheap.get(i + 1).compareTo(arrayheap.get(i)) > 0) {
                i = rightChild(k);
            }
            //如果当前索引的值比其孩子中最大的那个孩子的值还大，说明到终止条件了，跳出循环
            if (arrayheap.get(k).compareTo(arrayheap.get(i)) >= 0) {
                break;
            }
            //否则交换它和孩子的位置,并将i赋值给当前索引，准备下一轮循环
            arrayheap.swap(k, i);
            k = i;
        }
    }

我们在最大堆中取出元素，都是取出最大的那个元素(即顶部的那个元素)。当我们取出最大的元素后，将最后一个元素顶到顶部，将其原位置删除，然后和左右孩子比较，顶部元素肯定是和左右孩子中值最大的那个交换位置，所以我们得先判断一下左孩子和右孩子哪个的值大，得到结果后将顶部元素和最大的交换位置，具体看下图，有点绕口呀！

取出最大的元素(下图)：

将最后一个元素顶到顶部(下图)：

和左右孩子比较(下图)：

和值大的孩子交换位置(下图)：

继续和左右孩子比较(下图)：

交换位置(下图)：

比较，比孩子大，结束(下图)：

取出并替换堆中的最大元素

//找到堆中的最大元素，并且替换成元素e，返回最大元素
    public E replace(E e) {
        E ret = findMax();
        arrayheap.set(0, e);
        siftDown(0);
        return ret;
    }

我们可以通过通过extractMax()先取出堆中的的最大元素，然后在add，但是这样有2次O(logn)的操作，所以我们这里采用了另一种方法，找到堆中最大元素，直接调用数组自带的set()方法替换，然后通过siftDown()方法将其下沉。

将一组乱序的数组变成堆

我们先通过几个图了解步骤：

我们只要将不是叶子节点的节点逐个下沉就行，先从索引大的开始，最后到索引为0的即可。怎么找那个不是叶子节点的索引最大的节点？其实很简单，前面我们知道怎么找一个孩子的父节点的公式，这里可以直接用，因为我们知道该索引肯定是最后一个叶子节点的父节点。

下沉完成，终止(下图)：

找索引下的另一个节点开始下沉(下图)：

下沉完成，终止(下图)：

中间步骤省略，此为完成后的图(下图)：

分析结束，开始代码部分，我们写一个新的构造函数，接收传入的数组，先将DynamicGenericsArray添加一个新的构造函数

/**
     * 该构造函数用于堆中的将数组堆化
     * @param arr
     */
    public DynamicGenericsArray(E[] arr) {
        this.array = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            array[i] = arr[i];
        }
        size = arr.length;
    }

然后在我们自己的类中添加新的构造函数

/**
     * 将数组堆化
     * @param arr
     */
    public MaxHeap(E[] arr) {
        this.arrayheap = new DynamicGenericsArray<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

测试代码

对一个不是堆的数组堆化：

@Test
public void test() {
    int n = 1000000;
    Random random = new Random();
    Integer[] arr = new Integer[n];
    for (int i = 0; i < n; i++) {
        arr[i] = random.nextInt(Integer.MAX_VALUE);
    }
    long time1 = testHeap(arr, true);
    long time2 = testHeap(arr, false);
    System.out.println(time1);
    System.out.println(time2);
}

public static long testHeap(Integer[] arr, boolean isHeap) {
    long start = System.currentTimeMillis();
    MaxHeap<Integer> maxHeap = null;
    if (isHeap) {
        maxHeap = new MaxHeap<>(arr);
    } else {
        maxHeap = new MaxHeap<>();
        for (Integer num : arr) {
            maxHeap.add(num);
        }
    }
    long end = System.currentTimeMillis();
    return end - start;
}

测试结果

1
2

54
65

文章信息

时间	说明
2018-12-08	初稿