堆排序概念

堆排序是利用堆这种数据结构而设计的一种排序算法。时间复杂度为O(nlogn)。

堆排序具有如下性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为最大堆;或每个节点都小于或者等于其左右孩子节点被称为最小堆。

对堆中的节点进行编号,将这种逻辑映射到数组中,如下:


堆排序的基本性质:
最大堆:左右子节点小于父节点
最小堆:左右子节点大于父节点

堆排序流程

1.构建最大堆
构建最大堆之前呈现效果如下


构建最大堆之后呈现效果如下:

保证了堆排序中的最大堆的性质。
2.堆排序算法实现
取出构建最大堆中的最大值,放在尾部
然后重新构建最大堆。

以此类推最终达到从小到大的排序效果,完成堆排序。

PHP实现堆排序

<?php
    /**
    * 
    */
    class HeapSort 
    {
        public function __construct(&$arr) {
            $arr_length = count($arr)-1;
            $this->HeapMaxSort($arr,$arr_length);
        }
        private function HeapMaxSort(&$arr,$arr_length) {;
            $this->BuildMaxHeap($arr,$arr_length);

            for($i = $arr_length;$i >= 0; $i--) {
                $this->swap($arr,$i,0);
                $arr_length--;
                $this->MaxHeapify($arr,0,$arr_length);
            }
        }
        private function BuildMaxHeap(&$arr,$arr_length) {
            $count = count($arr)-1;
            for ($i = floor($count/2); $i >=0; $i--) {
                $this->MaxHeapify($arr,$i,$arr_length);
            }
        }

    public function MaxHeapify(&$arr,$i,$arr_length) {
            $left = $this->left($i);
            $right = $this->right($i);
            if($left <= $arr_length && $arr[$left] >= $arr[$i]) {
                $this->swap($arr,$i,$left);
                $largest = $left;
            } else {
                $largest = $i;
            }
            if ($right <= $arr_length && $arr[$right] >= $arr[$largest]) {
                $this->swap($arr,$largest,$right);
            $largest = $right;
            }
            if ($largest != $i) {
                $this->MaxHeapify($arr,$largest);
            }

        }
        public function swap(&$arr,$exist,$largest) {
            $temp = $arr[$exist];
            $arr[$exist] = $arr[$largest];
            $arr[$largest] = $temp;
        }
        private function left($i) {
            return 2*$i+1;
        }

        private function right($i) {
            return 2*$i+2;
        }


    }
    $array = array(5,2,3,1,4,6);
    $Heap_Model = new HeapSort($array);
    var_dump($array);