歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

尋找數組中前K個最小的數(Kth smallest element)---(堆排序的應用)

日常生活中我們總是遇到求解一個數組的最小值或者最大值等問題,這些問題基本上都可以在線性時間復雜度內完成,但是如果需要尋找數組的前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最大)下的應用,若有什麼不對的地方,還請指出,謝謝,歡迎拍磚。

Copyright © Linux教程網 All Rights Reserved