日常生活中我們總是遇到求解一個數組的最小值或者最大值等問題，這些問題基本上都可以在線性時間復雜度內完成，但是如果需要尋找數組的前K個最小值時該怎麼做呢？最一般的想法就是將數組排序，然後取出排序後的數組的前k個元素即可，這種算法的時間復雜度也就是排序的時間復雜度為O(NlogN)。但是仔細一想發現，我們沒有必要對所有的數進行排序，因為我們只用到了排序後的前K個數，為此可以考慮只找出排序的前K個數即可。這就讓我們聯想到了堆排序的過程。
堆排序分為兩部分，一部分是初始化建堆，另一部分是堆的調整，下面以建立小頂堆為例說明一下堆排序的過程。
堆是一個完整的二叉樹，小頂堆即堆頂是此樹的最小元素，小頂堆滿足父親節點小於所有的孩子節點。首先將數組看為一個完整二叉樹，然後根據堆的性質從第一個非葉子節點開始調整堆。
使用遞歸的方法對每個節點進行調整，直到調整到根節點為止。
堆建完之後，堆頂的元素即為數組的最小值，然後將其取出，將最後一位葉子元素放到堆頂，接著繼續調整堆，然後再取出堆頂元素，如此重復上述步驟K次，即可得到數組中前K個最小元素。
本文以K=2為例子實現了上述算法
建堆：
void Create_Heap(int* a, const int n)
{
for(int i=(n-1)/2; i>=0; i--)
{
Exchange_Node(a,n,i);
}
}
調整堆：
void Adjust_Heap(int* a, const int n, const int point)
{
for(int j=point; 2*j+1<n;)
{
if(j*2+2 < n)
{
int temp;
if(a[j] < a[2*j+1] && a[j] < a[2*j+2])
break;
else if(a[2*j+1] > a[2*j+2])
{
temp = 2*j+2;
}
else
{
temp = 2*j+1;
}
int temp_a = a[j];
a[j] = a[temp];
a[temp] = temp_a;
j = temp;
}
else
{
if(a[2*j+1] < a[j])
{
int temp = a[j];
a[j] = a[2*j+1];
a[2*j+1] = temp;
j = 2*j+1;
}
break;
}
}
}
找到前2個最小的數
int find_second_smallest(int* a, int n)
{
Create_Heap(a,n);
int temp;
temp = a[0];
a[0] = a[n-1];
a[n-1] = temp;
Adjust_Heap(a,n-1,0);
return a[0];
}
上述算法的性能分析：
假設總共有n=2^(k+1)個節點，則完全二叉樹有k+1層，從第k-1層開始調整，其中第k-1層有2^(k-1)個節點，每個節點需要調整1次(因為只用在第k-1層到第k層之間調整)，然後調整第k-2層，其中k-2層有2^(k-2)個節點，每個節點需要調整2次(從第k-2層調整到第k層)，……，最後調整根節點(0層元素)，有2^(0)個節點，每個節點需要調整k次，綜上所述在建堆的過程中總共需要調整的次數為2^(k-1)+2^(k-2)*2+2^(k-3)*3+……+2^(0)*k=2^(k+1)-2-k，其中k=logN，為此總的調整時間為O(N-2)，之後每次取出一個值只需要調整一次堆，所需時間即為堆的深度，所以查找第二小的元素所需時間為O(N + logN - 2)。
上述分析的基礎上我還實現了堆排序，代碼如下所示
void heap_sort(int* a, int n)
{
Create_Heap(a,n);
for(int i=n-1; i>0; i--)
{
int temp;
temp = a[0];
a[0] = a[i];
a[i] = temp;
Adjust_Heap(a,i,0);
}
}
測試代碼
void main()
{
int n;
cout<<"Input the num: ";
cin>>n;
while(n>0)
{
int* a = new int[n];
for(int i=n; i>0; i--)
a[n-i] = i;
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"The Second smallest num is: "<<find_second_smallest(a,n)<<endl;
cout<<"The Heap: ";
heap_sort(a,n);
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"Input the num: ";
cin>>n;
}
}
上述即為我對堆排序的一些理解，以及堆排序這種思維方式在查詢特定條件(第K最小或者第K最大)下的應用，若有什麼不對的地方，還請指出，謝謝，歡迎拍磚。
