常见排序算法总结 (五) - 堆排序与堆操作

堆排序（借助 API）

算法思想

利用堆能够维护数组中最大值的性质，根据数组元素建立最大堆，依次弹出元素并维护堆结构，直到堆为空。

稳定性分析

堆排序是不稳定的，因为堆本质上是完全二叉树，排序的过程涉及二叉树的父子节点交换，没有办法保证办法保证相等的值一定在同一棵子树上被处理。

具体实现

// Java 本身实现了优先队列的 API，其本质类似于堆，可以用来实现堆排序
private void heapSort(int[] arr) {
    Queue<Integer> queue = new PriorityQueue<>();
    for(int item : arr) {
        queue.offer(item);
    }
    for(int i = 0; i < arr.length; i++) {
        arr[i] = queue.poll();
    }
}

堆操作

上面的堆排序实现，有一种脑干缺失的美，图一乐就行。堆相关的内容中，堆的原理和操作显然更重要。

自顶向底建堆

自顶向底建堆，时间复杂度是 $O (Nl o g N)$ 这个量级的。自下而上的调整操作实现起来比较简单，原因是对于每个子节点而言，父节点是唯一的。

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {
    while (arr[cur] > arr[(cur - 1) / 2]) {
        // 当前元素大于父节点，那么进行交换并移动工作指针
        swap(arr, cur, (cur - 1) / 2);
        cur = (cur - 1) / 2;
    }
}

// 自顶向底建堆
private void buildHeap(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        upAdjust(arr, i);
    }
}

自底向顶建堆

自底向顶建堆，它的时间复杂度是 $O (N)$ 这个量级的。实现相对来说要更麻烦，原因是父节点可能有两个子节点，涉及到与谁交换的判断。

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
    // 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
    int child = 2 * cur + 1;
    while (child < size) {
        // 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
        int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
        // 再与当前节点比较大小
        target = arr[target] > arr[cur] ? target : cur;
        // 一旦发现此次操作中无需交换，立即停止流程
        if (target == cur) {
            break;
        }
        // 交换父子节点
        swap(arr, target, cur);
        // 移动工作指针
        cur = target;
        child = 2 * cur + 1;
    }
}

// 自底向顶建堆
private void buildHeap(int[] arr) {
    int n = arr.length;
    for (int i = n - 1; i >= 0; i--) {
        downAdjust(arr, i, n);
    }
}

堆排序（自己实现）

自顶向底建堆并实现排序

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {
    while (arr[cur] > arr[(cur - 1) / 2]) {
        // 当前元素大于父节点，那么进行交换并移动工作指针
        swap(arr, cur, (cur - 1) / 2);
        cur = (cur - 1) / 2;
    }
}

// 自顶向底建堆
private void buildHeap(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        upAdjust(arr, i);
    }
}

// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
    // 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
    int child = 2 * cur + 1;
    while (child < size) {
        // 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
        int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
        // 再与当前节点比较大小
        target = arr[target] > arr[cur] ? target : cur;
        // 一旦发现此次操作中无需交换，立即停止流程
        if (target == cur) {
            break;
        }
        // 交换父子节点
        swap(arr, target, cur);
        // 移动工作指针
        cur = target;
        child = 2 * cur + 1;
    }
}

// 堆排序
private void heapSort(int[] arr) {
    buildHeap(arr);
    int size = arr.length;
    // 不断地交换堆顶元素与堆中的最后一个元素，并向下调整维护堆
    while (size > 0) {
        swap(arr, 0, --size);
        downAdjust(arr, 0, size);
    }
}

自底向顶建堆并实现排序

// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {
    // 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
    int child = 2 * cur + 1;
    while (child < size) {
        // 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
        int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
        // 再与当前节点比较大小
        target = arr[target] > arr[cur] ? target : cur;
        // 一旦发现此次操作中无需交换，立即停止流程
        if (target == cur) {
            break;
        }
        // 交换父子节点
        swap(arr, target, cur);
        // 移动工作指针
        cur = target;
        child = 2 * cur + 1;
    }
}

// 自底向顶建堆
private void buildHeap(int[] arr) {
    int n = arr.length;
    for (int i = n - 1; i >= 0; i--) {
        downAdjust(arr, i, n);
    }
}

// 堆排序
private void heapSort(int[] arr) {
    buildHeap(arr);
    int size = arr.length;
    // 不断地交换堆顶元素与堆中的最后一个元素，并向下调整维护堆
    while (size > 0) {
        swap(arr, 0, --size);
        downAdjust(arr, 0, size);
    }
}

梳理总结

堆排序主要有两大步骤，包括建堆和出堆排序，其中建堆的操作根据方向的不同有效率上的差异，但是因为出堆排序需要 $O (Nl o g N)$ 量级的时间，所以总的时间复杂度为 $O (Nl o g N)$ 。
在实现的选择上，虽然自顶向底建堆本身相对比较容易实现，但是由于出堆排序的过程中一定会涉及到由上而下的调整，反而需要记忆更多的内容。因此，可以考虑只记住自底向顶建堆的实现方法。
事实上鉴于堆排序不具有稳定性，性能上也只是中规中矩，所以通常只有在考试遇到、要求实现不使用额外空间的情况下（随机快排需要额外的递归栈空间，大约是 $O (l o g N)$ 的水平；归并需要额外的辅助数组，是 $O (N)$ 的水平），会手写实现堆排序。
而在实际应用的过程中，空间换时间是常见操作，所以不需要额外空间的堆并没有什么优势。