/**
優先隊列的實現選擇：
            鏈表（表頭插入為O(N)，刪除時遍歷O(N)）或者讓表插入時保持排序
            二叉樹（刪除和插入都是O(logN)）

可以達到NlogN 的時間復雜度的排序，就是使用二叉堆實現
使用的排序算法就是堆排序
使用一個附加數組，存儲空間增加一倍  （或者將刪除的最小數放入堆的最后） //??
因為只會復制一次，時間復雜度并不會顯著增加                                                       //??
***/
// heapSort.h
//
//
pragma once
include "stdafx.h"
include <vector>
using namespace std;
int leftChild(int hole)  //查找節點的左子樹
{
    return hole*2 + 1;
}
// 最小值堆
template <typename T>
void percolateMinDown(int hole, vector<T>& vec) // vec為原數組，hole為當前要排序的堆的空穴
{
    int child;
    T temp = vec[hole];
    for (; leftChild(hole)< vec.size(); hole = child) 
    {
        child = leftChild(hole); //chlid為hole的左子樹，child+1為hole的右子樹
        if (leftChild(hole) != vec.size() && vec[child+1] < vec[child])   //注意數組訪問不要越界
        {
            child ++;   //取左子樹和右子樹中的最小值
        }
        if ( temp > vec[child])   //如果左子樹和右子樹中的最小值仍然比要空穴的值小，則其將最小值移到當前空穴
        {
            vec[hole] = vec[child];
        }
        else                     //如果左子樹和右子樹中的最小值仍然比要空穴的值大，則當前空穴就是其最終位置
            break;
    }
    vec[hole] = temp;
}
template <typename T>
void heapMinSort(vector<T>& vec)
{
//     vector<T> tempVector(vec.size()+1);
//     for (int i = 0; i < vec.size(); i++)
//     {
//         tempVector[i] = vec[i];   //這里并沒有用到附加數組
//     }
    int hole = vec.size()/2;
    for (; hole >= 0; hole--) // 從大到小依次計算空穴的值
    {
        percolateMinDown(hole,vec);
    }

}
// 最大值堆
template <typename T>
void percolateMaxDown(int hole, vector<T>& vec)
{
    int child;
    T temp = vec[hole];
    for (;leftChild(hole) < vec.size(); hole = child)
    {
        child = leftChild(hole);
        if ( leftChild(hole) != vec.size() && vec[child] < vec[child+1]) //大根堆中取兩個子樹的較大者
        {
            child++;
        }
        if (temp < vec[child])                                            //將左子樹和右子樹中的較大者移入空穴
        {
            vec[hole] =  vec[child];
        }
        else
            break; 
    }
    vec[hole] = temp;
}
template <typename T>
void heapMaxSort(vector<T>& vec)
{
    int hole = vec.size()/2;
    for (; hole >= 0; hole--) // 從大到小依次計算空穴的值
    {
        percolateMaxDown(hole,vec);
    }

}</pre>