堆

[yifanzheng]

堆

堆是一种特殊的树，它满足如下两个特点：

• 堆是一个完全二叉树；
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”；对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。

堆这种数据结构几个非常重要的应用：优先级队列（合并 k 个有序文件）、求 Top K 和求中位数。

实践

• 实现大顶堆
• 堆排序

[yifanzheng]

实现大顶堆

因为堆是一个完全二叉树，所以适合使用数组来存储，用数组来存储完全二叉树是非常节省存储空间的。

下面是添加操作和删除堆顶元素的堆化流程：

往堆中添加元素

从下往上堆化

删除堆顶元素

从上往下堆化

代码实现

/**
 * 大顶堆实现（小顶堆实现类似）
 *
 * @author star
 */
public class MaxHeap {

    private int[] datas;
    private int capacity;
    private int count;

    public MaxHeap(int capacity) {
        this.datas = new int[capacity + 1];
        this.capacity = capacity;
        this.count = 0;
    }

    public MaxHeap(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("arr cannot be null");
        }
        int len = arr.length;
        this.datas = new int[len + 1];
        this.capacity = len;
        this.count = len;
        System.arraycopy(arr, 0, this.datas, 1, len);
        this.buildHeap();
    }

    /**
     * 添加数据到堆中
     *
     * @param data
     */
    public void add(int data) {
        // 堆满了
        if (count >= capacity) {
            return;
        }
        // 将数据添加到堆的末尾
        datas[++count] = data;
        // 从下往上进行堆化
        shiftUpHeapify(count);
    }

    /**
     * 获取堆顶的元素
     */
    public int getMax() {
        if (count <= 0) {
            throw new NoSuchElementException("max heap is empty");
        }
        return datas[1];
    }

    /**
     * 从堆中取出堆顶元素，即堆中所存储的最大数据
     *
     * @return 堆顶元素
     */
    public int extractMax() {
        if (count <= 0) {
            throw new NoSuchElementException("max heap is empty");
        }
        int res = datas[1];
        // 将末尾元素放到堆顶
        datas[1] = datas[count];
        count--;
        // 从上往下进行堆化
        shiftDownHeapify(1);
        return res;
    }

    private void buildHeap() {
        // 从上往下进行堆化
        for (int i = count / 2; i >= 1; i--) {
            shiftDownHeapify(i);
        }
    }

    /**
     * 从上往下进行堆化
     */
    private void shiftDownHeapify(int pos) {
        while (2 * pos <= count) {
            int maxPos = 2 * pos;
            // 确定 datas[2*pos] 和 data[2*pos+1] 中的最大值
            if (maxPos + 1 <= count && datas[maxPos] < datas[maxPos + 1]) {
                maxPos++;
            }
            // 如果左右节点都不大于 pos 节点，则停止轮询
            if (datas[maxPos] <= datas[pos]) {
                break;
            }
            // 交换位置
            swap(pos, maxPos);
            pos = maxPos;
        }
    }

    /**
     * 从下往上进行堆化
     */
    private void shiftUpHeapify(int pos) {
        while (pos > 1 && datas[pos] > datas[pos / 2]) {
            swap(pos, pos / 2);
            pos = pos / 2;
        }
    }

    private void swap(int n, int m) {
        int temp = datas[n];
        datas[n] = datas[m];
        datas[m] = temp;
    }
}

[yifanzheng]

堆排序

堆排序是原地排序算法，包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

代码实现

/**
 * 堆排序
 *
 * @author star
 */
public class HeapSort {

    private HeapSort() {

    }

    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 1. 构建大顶堆
        // 由于堆是从0开始索引的，所以需要向前移动一位
        for (int i = len / 2 - 1; i >= 0; i--) {
            shiftDownHeapify(arr, i, len);
        }
        // 2. 排序
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, 0, i);
            shiftDownHeapify(arr, 0, i);
        }
    }

    /**
     * 从上往下进行堆化
     */
    private static void shiftDownHeapify(int[] arr, int pos, int len) {
        while (2 * pos + 1 < len) {
            int maxPos = 2 * pos + 1;
            if (maxPos + 1 < len && arr[maxPos + 1] > arr[maxPos]) {
                maxPos++;
            }
            if (arr[maxPos] <= arr[pos]) {
                break;
            }
            swap(arr, pos, maxPos);
            pos = maxPos;
        }
    }

    private static void swap(int[] arr, int n, int m) {
        int temp = arr[n];
        arr[n] = arr[m];
        arr[m] = temp;
    }

}