章节三：堆排序
（二叉）堆数据结构是一种数组对象，可被视为一颗完全二叉树，假设给定某个节点的下标i，则其父节点Parent(i)，左孩子Left(i)、右孩子Right(i)有如下关系式（此处下标从0开始计数）：
Parent(i)=i/2; Left(i)=2*i+1; Right(i)=2*i+2;
二叉堆有两种：最大堆和最小堆；在最大堆中除了根节点以外的每个节点i，都有A【Parent(i)】>=A[i]，反之即为最小堆。注：在堆排序算法中，我们使用最大堆；最小堆通常在构造优先队列时使用。
假定Left(i)和Right(i)为根的两颗二叉树都是最大堆，但A[i]可能小于其子女，Max_Heapify递归的让A[i]下降，使以i为根的子树成为最大堆。
//Max_Heapify PHP实现
function Max_Heapify(&$array,$i,$heap_size,$cmp_function='strcmp'){
$left=2*$i+1; $right=2*$i+2;
$largest=$i;
if($left<$heap_size&&call_user_function($cmp_function,$array[$left],$array[$i])<1){
$largest=$left;
}
if($right<$heap_size&&call_user_function($cmp_function,$array[$right],$array[$largest])<1){
$largest=$right;
}
if($i!=$largest){
swap($array[$i],$array[$largest]);
Max_Heapify($array,$largest,$heap_size,$cmp_function);
}
}
i节点的子树大小至多为2n/3(最底层恰好半满)，则Max_Heapify运行时间可用公式描述：T(n)<=T(2n/3)+O(1) ===>T(n)=O(lgn);
建堆：
可自底而上的用Max_Heapify将数组A[0...n-1]变成一个大顶堆。由于子数组A【n/2.....n-1】全是树中的叶子节点，可看作只含有一个元素的堆。
//Build_Max_Heap PHP实现
function Build_Maxheap(&$array){
$heap_size=count($array);
for($i=(int)(heap_size/2);$i>=0;$i--){
Max_Heapify($array,$i,$head_size);
}
}
经证明，Build_Max_Heap可以在线性时间内将一个无序数组建成一个最大/最小堆：O(n)。
堆排序：堆排序算法首先在线性时间内建立一个大顶堆，此时栈顶元素即为数组最大值，swap(arr[n-1],arr[0])，此时新的根元素违背了最大堆的性质，可通过Max_Heapfy(arr,0,heap_size)保持这一性质，循环往复。
//堆排序 heap_sort PHP实现
function heap_sort(&$array){
$heap_size=count($array);
Build_Max_Heap($array);
for($i=$heap_size-1;$i>=1;$i--){
swap($array[$i],$array[0]);
Max_Heapify($array,0,--$heap_size);
}
}
堆排序时间性能：最好、最坏、平均情况下均为O(nlgn)；空间复杂度O(1);不稳定排序；
堆排序虽然是个不错的算法，但实际中快速排序的实现往往优于堆排序。尽管如此，堆数据结构依然有很大用处，比如常见的：作为高效的优先队列。
基于最大堆实现的最大优先级队列：
一个最大优先级队列应支持的操作：
INSERT(S,x): 元素x插入集合S； MaxIMUM(S): 返回S中最大关键字元素。EXTRACT_MAX(S):去掉并返回S中具有最大关键字的元素。INCREMENT-KEY(S,x,k):将位置x的关键字值增大为k;
class MaxPriority{
private $array;//优先值数组
protected $error;
public function getError(){
return $this->error;
}
public function getArray(){
return $this->array;
}
public function MaxiMum(){
if(empty($this->$array)){
$this->error="Priority Heap is empty~~";
return false;
}
return $this->$array[0];
}
public function ExtractMax(){
$heap_size=count($this->array);
if ($heap_size<1) {
$this->error="heap underflow";
return false;
}
$max=$this->array[0];
$heap_size-=1;
if ($heap_size==0) {
$this->array=array();
}else{
$this->array[0]=$this->array[$heap_size-1];
Max_Heapify($this->array,0,$heap_size);
}
return $max;
}
public function Increment_Key($i,$key){
if($this->array[$i]<$key){
$this->error="new key is smaller than current key";
return false;
}
$this->array[$i]=$key;
while ($i>0&&$this->array[(int)($i/2)]<$this->array[$i]) {
swap($this->array[(int)($i/2)],$this->array[$i]);
$i=(int)($i/2);
}
}
public function Heap_insert($key){
$heap_size=count($this->getArray());
$heap_size=$heap_size+1;
$this->array[]=0;//负无穷
$this->Increment_Key($heap_size-1,$key);
}
}
综上可知：大小集合为n的堆可以在O(lgn)时间内完成任意优先队列操作。
