/**************************优先队列的实现选择：			链表（表头插入为O(N)，删除时遍历O(N)）或者让表插入时保持排序			二叉树（删除和插入都是O(logN)）	可以达到NlogN 的时间复杂度的排序，就是使用二叉堆实现使用的排序算法就是堆排序使用一个附加数组，存储空间增加一倍  （或者将删除的最小数放入堆的最后） //??因为只会复制一次，时间复杂度并不会显著增加														//??***************************/// heapSort.h////#pragma once#include "stdafx.h"#include 
    
     using namespace std;int leftChild(int hole)  //查找节点的左子树{	return hole*2 + 1;}// 最小值堆template 
     
      void percolateMinDown(int hole, vector
      
       & 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 
       
        void heapMinSort(vector
        
         & vec){// 	vector
         
           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 
          
           void percolateMaxDown(int hole, vector
           
            & 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 
            
             void heapMaxSort(vector
             
              & vec){ int hole = vec.size()/2; for (; hole >= 0; hole--) // 从大到小依次计算空穴的值 { percolateMaxDown(hole,vec); } }