堆積排序

堆積排序
堆積排序
	堆積排序演算法的演示。首先，將元素進行重排，以符合堆積的條件。圖中排序過程之前簡單地繪出了堆積樹的結構。
概況
類別	排序演算法
資料結構	陣列
複雜度
平均時間複雜度
最壞時間複雜度
最佳時間複雜度
空間複雜度	total, auxiliary
最佳解	不是
相關變數的定義

堆積排序（英語：Heapsort）是指利用堆積這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。

概述

若以升序排序說明，把陣列轉換成最大堆積（Max-Heap Heap），這是一種滿足最大堆積性質（Max-Heap Property）的二叉樹：對於除了根之外的每個節點i, A[parent(i)] ≥ A[i]。

重複從最大堆積取出數值最大的結點（把根結點和最後一個結點交換，把交換後的最後一個結點移出堆積），並讓殘餘的堆積維持最大堆積性質。

堆積節點的訪問

通常堆積是通過一維陣列來實現的。在陣列起始位置為0的情形中：

父節點i的左子節點在位置 $(2i+1)$ ;
父節點i的右子節點在位置 $(2i+2)$ ;
子節點i的父節點在位置 $\lfloor (i-1)/2\rfloor$ ;

堆積的操作

在堆積的資料結構中，堆積中的最大值總是位於根節點（在優先佇列中使用堆積的話堆積中的最小值位於根節點）。堆積中定義以下幾種操作：

最大堆積調整（Max Heapify）：將堆積的末端子節點作調整，使得子節點永遠小於父節點
建立最大堆積（Build Max Heap）：將堆積中的所有數據重新排序
堆積排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆積調整的遞歸運算

實作範例

C語言

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比较
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    int i;
    // 初始化，i從最後一個父節點開始調整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    // 初始化，i從最後一個父節點開始調整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

Java

import java.util.Arrays;

public class HeapSort {
    private int[] arr;
    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort() {
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (arr.length >> 1)- 1;
        for (int i = beginIndex; i >= 0; i--)
            maxHeapify(i, len);
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = len; i > 0; i--) {
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

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

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index, int len) {
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。
        if (li > len) return;      // 左子节点索引超出计算范围，直接返回。
        if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if (arr[cMax] > arr[index]) {
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

    /**
     * 测试用例
     *
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[] {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }
}

Python

#!/usr/bin/env python
#-*-coding:utf-8-*-


def heap_sort(lst):
    def sift_down(start, end):
        """最大堆调整"""
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and lst[child] < lst[child + 1]:
                child += 1
            if lst[root] < lst[child]:
                lst[root], lst[child] = lst[child], lst[root]
                root = child
            else:
                break

# 創建最大堆

    for start in range((len(lst) - 2) // 2, -1, -1):
        sift_down(start, len(lst) - 1)

# 堆排序
    for end in range(len(lst) - 1, 0, -1):
        lst[0], lst[end] = lst[end], lst[0]
        sift_down(0, end - 1)
    return lst



if __name__ == "__main__":
    l = [9, 2, 1, 7, 6, 8, 5, 3, 4]
    heap_sort(l)

JavaScript

Array.prototype.heap_sort = function() {
	var arr = this.slice(0);
	function swap(i, j) {
		var tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	function max_heapify(start, end) {
		//建立父節點指標和子節點指標
		var dad = start;
		var son = dad * 2 + 1;
		if (son >= end)//若子節點指標超過範圍直接跳出函數
			return;
		if (son + 1 < end && arr[son] < arr[son + 1])//先比較兩個子節點大小，選擇最大的
			son++;
		if (arr[dad] < arr[son]) {//如果父節點小於子節點時，交換父子內容再繼續子節點和孫節點比較
			swap(dad, son);
			max_heapify(son, end);
		}
	}

	var len = arr.length;
	//初始化，i從最後一個父節點開始調整
	for (var i = Math.floor(len / 2) - 1; i >= 0; i--)
		max_heapify(i, len);
	//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
	for (var i = len - 1; i > 0; i--) {
		swap(0, i);
		max_heapify(0, i);
	}

	return arr;
};
var a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6];
console.log(a.heap_sort());

PHP

<?php
function swap(&$x, &$y) {
	$t = $x;
	$x = $y;
	$y = $t;
}

function max_heapify(&$arr, $start, $end) {
	//建立父節點指標和子節點指標
	$dad = $start;
	$son = $dad * 2 + 1;
	if ($son >= $end)//若子節點指標超過範圍直接跳出函數
		return;
	if ($son + 1 < $end && $arr[$son] < $arr[$son + 1])//先比較兩個子節點大小，選擇最大的
		$son++;
	if ($arr[$dad] <= $arr[$son]) {//如果父節點小於子節點時，交換父子內容再繼續子節點和孫節點比較
		swap($arr[$dad], $arr[$son]);
		max_heapify($arr, $son, $end);
	}
}

function heap_sort($arr) {
	$len = count($arr);
	//初始化，i從最後一個父節點開始調整
	for ($i = ceil($len/2) - 1; $i >= 0; $i--)
		max_heapify($arr, $i, $len);
	//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
	for ($i = $len - 1; $i > 0; $i--) {
		swap($arr[0], $arr[$i]);
		max_heapify($arr, 0, $i);
	}
	return $arr;
}

$arr = array(3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6);
$arr = heap_sort($arr);
for ($i = 0; $i < count($arr); $i++)
	echo $arr[$i] . ' ';
?>

Go

package main

import (
	"fmt"
)

func HeapSort(array []int) {
	m := len(array)
	s := m/2
	for i := s; i > -1; i-- {
		heap(array, i, m-1)
	}
	for i := m-1; i > 0; i-- {
		array[i], array[0] = array[0], array[i]
		heap(array, 0, i-1)
	}
}

func heap(array []int, i, end int){
	l := 2*i+1
	if l > end {
		return
	}
	n := l
	r := 2*i+2
	if r <= end && array[r]>array[l]{
		n = r
	}
	if array[i] > array[n]{
		return
	}
	array[n], array[i] = array[i], array[n]
	heap(array, n, end)
}

func main()  {
	array := []int{
		55, 94,87,1,4,32,11,77,39,42,64,53,70,12,9,
	}
	HeapSort(array)
	fmt.Println(array)
}

Julia (程式語言)

function HeapSort(array)
    function adjust(l,u)
        while true
            j = 2*l # 左子點
            if (j>u) # 代表沒有子點
                break
            end 
            if ((j+1) <= u) # 有右子點
                if (array[j] < array[j+1]) 
                    j += 1 #比較左右子點
                end
            end
            if (array[j] > array[l]) #比較父點跟子點
                 array[l], array[j]= array[j], array[l]
                 l = j # 有交換
            else
                break # 沒交換跳出迴圈
            end
        end
    end
    n = length(array)
    for i in n:-1:1 # 建 max Heap
        adjust(i,n)
    end 
    #持續把第一個(最大)的元素最後一個交換
    array[n],array[1]=array[1],array[n] 
    for i in n-1:-1:1
        adjust(1,i)
        array[i],array[1]=array[1],array[i]
    end
    return array
end

Rust

fn max_heapify<T: Ord + Copy>(data: &mut [T], pos: usize, end: usize) {
    let mut dad = pos;
    let mut son = dad * 2 + 1;
    while son <= end {
        if son < end && data[son] < data[son + 1] {
            son += 1;
        }
        if data[dad] > data[son] {
            return;
        } else {
            data.swap(dad, son);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

fn heap_sort<T:Ord+Copy>(data: &mut[T]) {
    let len = data.len();
    for i in (0..=len / 2 - 1).rev() {
        max_heapify(data, i, len - 1);
    }
    for i in (1..=len - 1).rev() {
        data.swap(0, i);
        max_heapify(data, 0, i - 1);
    }
}

fn main() {
    let mut nums = vec![9, 2, 1, 7, 6, 8, 5, 3, 4];
    heap_sort(nums.as_mut_slice());
}

原地堆積排序

基於以上堆積相關的操作，我們可以很容易的定義堆積排序。例如，假設我們已經讀入一系列數據並建立了一個堆積，一個最直觀的演算法就是反覆的呼叫del_max()函數，因為該函數總是能夠返回堆積中最大的值，然後把它從堆積中刪除，從而對這一系列返回值的輸出就得到了該序列的降序排列。真正的原地堆積排序使用了另外一個小技巧。堆積排序的過程是：

建立一個堆積 $H[0..n-1]$
把堆積首（最大值）和堆積尾互換
把堆積的尺寸縮小1，並呼叫shift_down(0),目的是把新的陣列頂端數據調整到相應位置
重複步驟2，直到堆積的尺寸為1

平均複雜度

堆積排序的平均時間複雜度為 $\mathrm {O} (n\log n)$ ，空間複雜度為 $\Theta (1)$ 。

參考

^ R. Schaffer, R. Sedgewick. The Analysis of Heapsort. Journal of Algorithms. 1993-07, 15 (1): 76–100 [2022-10-02]. doi:10.1006/jagm.1993.1031. （原始內容存檔於2022-01-27）（英語）.

外部連結

常見排序演算法 - 堆積排序 (Heap Sort)
堆積演算法的視覺化演示可以直觀看到堆積演算法的操作

[1] R. Schaffer, R. Sedgewick. The Analysis of Heapsort. Journal of Algorithms. 1993-07, 15 (1): 76–100 [2022-10-02]. doi:10.1006/jagm.1993.1031. （原始內容存檔於2022-01-27）（英語）.

[1]

閱論編排序演算法
理論	計算複雜性理論大O符號全序關係數據結構術語列表原地演算法穩定性比較排序自適應排序（英語：Adaptive sort）排序網絡（英語：Sorting network）整數排序（英語：Integer sorting） X+Y排序（英語：X + Y sorting）量子排序（英語：Quantum sort）
交換排序	泡沫排序雞尾酒排序奇偶排序梳排序侏儒排序快速排序慢速排序臭皮匠排序 Bogo排序
選擇排序	選擇排序堆積排序平滑排序（英語：Smoothsort）笛卡爾樹排序（英語：Cartesian tree sort）錦標賽排序（英語：Tournament sort）圈排序（英語：Cycle sort）弱堆積排序（英語：Weak heap）
插入排序	插入排序希爾排序伸展排序二叉搜尋樹排序圖書館排序耐心排序
合併排序	合併排序梯級合併排序（英語：Cascade merge sort）振盪合併排序（英語：Oscillating merge sort）多相合併排序（英語：Polyphase merge sort）
分佈排序	美國旗幟排序（英語：American flag sort）珠排序桶排序爆炸排序（英語：Burstsort）計數排序比較計數排序插值排序鴿巢排序相鄰圖排序（英語：Proxmap sort）基數排序閃電排序（英語：Flashsort）
並行排序	雙調排序器（英語：Bitonic sorter） Batcher合併網絡兩兩排序網絡（英語：Pairwise sorting network）
混合排序	塊排序（英語：Block sort） Tim排序內省排序 Spread排序（英語：Spreadsort）合併插入排序（英語：Merge-insertion sort）
其他	拓撲排序煎餅排序意粉排序（英語：Spaghetti sort）