PHP堆排序實作程式碼

小云云原創: 2018-03-22 09:31:401434瀏覽

堆可以視為一棵完全的二元樹,除了最底層之外,每一層都是滿的,這使得堆可以利用數組來表示,每一個結點對應數組中的一個元素。
陣列與堆之間的關係：
二元堆一般分為兩種：最大堆和最小堆。
最大堆：堆中每個父節點的元素值都大於等於其孩子結點（如果存在）；

#最小堆：堆中每個父節點的元素值都小於等於其孩子結點（如果存在）；

什麼是堆排序

堆排序（假設利用最大堆）就是把堆頂的最大數取出,將剩餘的堆繼續調整為最大堆

堆排序演算法

建堆：建堆是不斷調整堆的過程，從len/2 開始調整，一直到第一個節點，此處len 是堆中元素的個數。建堆的過程是線性的過程，從len/2 到0 處一直呼叫調整堆的過程，相當於o(h1) + o(h2) …+ o(hlen/2) 其中h 表示節點的深度，len /2 表示節點的個數，這是一個求和的過程，結果是線性的O(n)。

調整堆：調整堆在建構堆的過程中會用到，在堆排序過程中也會用到。利用的想法是比較節點i和它的孩子節點left(i) , right(i)，選出三者最大(或最小)者，如果最大（小）

值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然後再呼叫調整堆過程，這是一個遞歸的過程。調整堆的過程時間複雜度與堆的深度有關係，是 logn 的操作，因

為是沿著深度方向進行調整的。

堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素來建構堆。然後將堆的根節點取出(一般是與最後一個節點進行交換)，將前面len-1 個節點繼續進行堆調整的過

程，然後再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間複雜度是 O(nlogn)。因為建堆的時間複雜度是O(n)（呼叫一次）；調整堆的時間複雜度是logn，調

用了n-1 次，所以堆排序的時間複雜度是O( nlogn)。

範例：

<?php
// PHP 堆排序算法实现、堆排序时间复杂度分析
/**
 * 堆排序
 * @param array $arr
 */
function heap_sort(array &$arr)
{
    $count = count($arr);
    // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点)
    for($i = floor($count / 2) - 1; $i >= 0; $i --)
    {
        heap_adjust($arr, $i, $count);
    }
    // 调整堆
    for($i = $count - 1; $i >= 0; $i--)
    {
        //将堆顶元素与最后一个元素交换
        swap($arr,0,$i);
        heap_adjust($arr,0,$i - 1);
    }
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $a 数组下标
 * @param int $b 数组下标
 */
function swap(array &$arr, $a, $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $start 数组下标
 * @param int $end 数组下标
 */
function heap_adjust(array &$arr, $start, $end)
{
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
    for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
    {
        if($j != $end && $arr[$j] < $arr[$j + 1])
        {
            $j ++;
        }
        if($temp < $arr[$j])
        {
	        //将根节点设置为子节点的较大值
	        $arr[$start] = $arr[$j];
	        $start = $j;
        }
    }
    $arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);

輸出：

Array ( [0] => 1 [1] => 2 [2] => 3 [3] = > 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 9 )

#時間複雜度分析

整體來說，堆排序的時間複雜度是O(nlogn)。由於堆排序對原始記錄的排序狀態並不敏感，因此它無論是最好、最差和平均時間複雜度都是 O(nlogn)。這在性能上顯然要遠遠好於冒泡、簡單選擇、直接插入的 O(n^2) 的時間複雜度了。
堆排序是一種不穩定排序方法(排序前後相同元素的前後順序可能改變)。

PHP堆排序實作程式碼

什麼是堆排序

堆排序演算法

#時間複雜度分析

相關文章