/**************************
優(yōu)先隊列的實現(xiàn)選擇：
            鏈表（表頭插入為O(N)，刪除時遍歷O(N)）或者讓表插入時保持排序
            二叉樹（刪除和插入都是O(logN)）
     
可以達到NlogN 的時間復雜度的排序，就是使用二叉堆實現(xiàn)
使用的排序算法就是堆排序
使用一個附加數(shù)組，存儲空間增加一倍  （或者將刪除的最小數(shù)放入堆的最后） //??
因為只會復制一次，時間復雜度并不會顯著增加                                                       //??
***************************/
 
// heapSort.h
//
//
#pragma once
#include "stdafx.h"
#include <vector>
 
using namespace std;
 
 
 
int leftChild(int hole)  //查找節(jié)點的左子樹
{
    return hole*2 + 1;
}
// 最小值堆
template <typename T>
void percolateMinDown(int hole, vector<T>& vec) // vec為原數(shù)組，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])   //注意數(shù)組訪問不要越界
        {
            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];   //這里并沒有用到附加數(shù)組
//     }
    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);
    }  
}

標簽：

版權申明：本站文章部分自網絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。