/**************************
优先队列的实现选择：
            链表（表头插入为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);
    }  
}