[数据结构与算法]算法基础（五）– 堆结构与堆排序

实现大顶堆

大顶堆要求父元素要大于两个子元素，且对于子树有同样要求。

public static class MyHeap {
    // 记录堆的元素数据存储数组
    private int[] heap;

    // 记录堆的总容量
    private final int limit;

    // 记录有效元素数量
    private int heapSize;

    public MyHeap(int limit) {
        this.heap = new int[limit];
        this.limit = limit;
        this.heapSize = 0;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public boolean isFull() {
        return heapSize == limit;
    }

    public void push(int value) {
        if (heapSize == limit) {
            throw new RuntimeException("heap is full");
        }

        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    public int pop() {
        int res = heap[0];
        // 注意先将size减一，因为下标比长度小 1
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return res;
    }

    /**
     * 向下调整index位置元素至满足大顶堆的要求
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            // index需要与两个孩子比出最大值
            // 先从孩子中选出最大值
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            // 调整
            if (largest == index) {
                break;
            }

            swap(arr, largest, index);
            index = largest;
            // 要更新左孩子的位置信息，如果没有孩子，while循环判断直接退出，否则，根据孩子中数组信息更新。
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

实现堆排序

实现堆结构后，依次取出元素更新到合适数组位置后，即可实现数组有序。

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }

    int heapSize = arr.length;
    while (heapSize > 0) {
        swap(arr, 0, --heapSize);
        heapify(arr, 0, heapSize);
    }
}

/**
 * index 新增末尾的节点，向上比较，原数组上构建堆
 *
 * @param arr
 * @param index
 */
private static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

/**
 * 向下调整index位置元素至满足大顶堆的要求
 *
 * @param arr
 * @param index
 * @param heapSize
 */
private static void heapify(int[] arr, int index, int heapSize) {
    int left = (index * 2) + 1;
    while (left < heapSize) {
        int largest = (left + 1) < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }

        swap(arr, index, largest);
        index = largest;
        left = index * 2 + 1;
    }
}

上述堆排序算法中，构建堆过程时间复杂度是 O(N*log N) 。如果我们已知了要构建的所有元素，是可以通过 heapify 方法进一步优化构建堆的过程的，使其复杂度变为 O(n) 。

优化构建堆

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    //for (int i = 0; i < arr.length; i++) {
    //    heapInsert(arr, i);
    //}

    // 从底部构建堆，最后一层元素因为无法下沉，因此复杂度为O(1)，然后逐层向上底层，但要下沉的数量逐层减少，因此复杂度为 O(n)
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }

    int heapSize = arr.length;
    while (heapSize > 0) {
        swap(arr, 0, --heapSize);
        heapify(arr, 0, heapSize);
    }
}

小结

本篇文章是对堆结构的入门，以及在排序算法上的应用，相信在熟悉了对结构后，完成堆排序丝毫不在话下，然后构建堆其实有两种方式，如果我们一次性知道了所有要构建堆的元素的情况下，使用 heapify 下沉方法，借助底层元素更多的优势，效率是更优的，而如果我们只是逐步构建，无法知道所有元素的情况下，只能使用 heapInsert 方法，先将元素插入到末尾，然后不断与父节点比较、向上冒泡来构建堆。

其实，掌握了heapInsert、heapify两个方法，也就会用了堆结构。