堆排序

[codcodog]

堆排序

堆

堆（英语：Heap） 是计算机科学中一类特殊的数据结构的统称。堆 通常是一个可以被看作一棵树的数组对象。

逻辑定义

N个元素序列{k1, k2...ki...kn}，当且仅当满足下列关系时称之为堆：
(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4... n/2)

性质

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）
• 堆总是一颗完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入

详细参考：堆（数据结构） Wiki

堆排序

堆排序（Heapsort） 是指利用 堆 这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子节点的键值或索引总是小于（或大于）它的父节点。

堆的操作

• 最大堆调整（Max Heapify）：将堆的末端子节点作調整，使得子节点永远小于父节点
• 建立最大堆（Build Max Heap）：将堆所有数据重新排序
• 堆排序（Heapsort）：移除位于第一个数据的根节点，并做最大堆調整的递回运算

详细参考：堆排序 Wiki

代码实现

PHP 版本

<?php
/**
 * 最大堆调整
 *
 * @param   array
 * @param   int
 * @param   int
 * @return  void
 */
function max_heapify(&$arr, $i, $end)
{
    $dad = $i;
    $son = $i * 2 + 1;

    // 没有子节点
    if ($son >= $end) return;

    // 取两个子节点中最大的那个
    ($son + 1 < $end && $arr[$son+1] > $arr[$son]) and $son++;

    // 如果父节点小于子节点，则交换它们的值
    if ($arr[$dad] < $arr[$son]) {
        list($arr[$dad], $arr[$son]) = [$arr[$son], $arr[$dad]];

        // 继续比较子节点和它的子孙节点
        max_heapify($arr, $son, $end);
    }
}

/**
 * 堆排序
 *
 * @param   array
 * @return  void
 */
function heap_sort(&$arr)
{
    $len = count($arr);

    // i 从最后一个父节点开始調整
    for ($i = floor($len / 2 - 1); $i >= 0; $i--) {
        max_heapify($arr, $i, $len);
    }

    // 移除位于第一个数据的根节点，并做最大堆調整递回运算
    for ($i = $len - 1; $i >= 0; $i--) {
        list($arr[0], $arr[$i]) = [$arr[$i], $arr[0]];
        max_heapify($arr, 0, $i);
    }
}


$arr = [2, 1, 7, 6, 5, 3, 4];
heap_sort($arr);

foreach ($arr as $v) {
    echo $v . ' ';
}

# 输出 1 2 3 4 5 6 7 

Python 版本

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

def main():
    l = [2, 1, 7, 6, 5, 3, 4]
    heap_sort(l)
    print(l)

if __name__ == "__main__":
    main()

# 输出 [1, 2, 3, 4, 5, 6, 7]