堆排序
堆排序即利用堆的思想來進行排序,
總共分為兩個步驟:
1. 建堆 升序:建大堆;? ?降序:建小堆
2 .利用堆刪除思想來進行排序
利用堆刪除思想來進行排序 建堆和堆刪除中都用到了向下調整,因此掌握了向下調整,就可以完成堆排序。
建堆
我們建堆的也利用我們的向下調整來建立我們的堆,但是我們不從我們的根開始,因為如果從根開始的話可以用我們的向上調整建堆,但是時間會比我們的向下調整建堆。
我們向下調整的是用是從底下開始,使我們的分支是一個堆,然后在使我們的整體是一個堆。
向下調整來排序
這里的排序和我們的堆的數據的刪除相似。我們將我們的根和數組的最后一個元素進行交換后,我們的count--,在將剩下的元素進行向下調整,那么數組的最后的數字就是我們的最大的數字或者最小的數字。我們進行調整完我們堆 的根就是我們第二小(大)的數字,如此在進行交換和調整這樣我們的數組就會變成有序的(升序或者降序)(我們這里寫的是降序)。
總代碼:
//對數組進行堆排序
void HeapSort(int* a, int n)
{//建堆int i = 0;int count = n;for (i = (n-1-1)/2; i>=0; i--){AdjustDown(a, i, n);}for (i = 0; i < n; i++){Swag(&a[0], &a[n - i - 1]);count--;AdjustDown(a, 0,count );}
}
Topk問題
TOP-K問題:即求數據結合中前K個最大的元素或者最小的元素,一般情況下數據量都比較大。 比如:專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題,能想到的最簡單直接的方式就是排序,但是:如果數據量非常大,排序就不太可取了(可能 數據都不能一下子全部加載到內存中)。
最佳的方式就是用堆來解決,基本思路如下:
1. 用數據集合中前K個元素來建堆 前k個最大的元素,則建小堆 前k個最小的元素,則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較,不滿足則替換堆頂元素。
當我們所有的數據比完后,這個堆中就只剩下我們的最大的或者最小的前k個數。這樣需要的空間不會很大。
代碼:
//創建數據,放在文件里面,隨機數。
void CreakData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("FILE* fin eorror");return;}srand((unsigned int)time(0));int i = 0;for (i = 0; i < 100000; i++){int count = rand() % 100000;fprintf(fin, "%d ", count);}fclose(fin);}
//解決topk問題
void PrintTopK(int k)
{//topK問題int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("malloc");}int i = 0;int count = 0;//創建數據/*CreakData();*///打開文件FILE* fin = fopen("data.txt", "r");if (fin == NULL){perror("fopen!");return;}//讀取前面k個數字for (i = 0; i < k; i++){fscanf(fin, "%d", &topk[i]);}//建堆for (i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, i, k);}//開始往后面讀取數字,如果比我們的堆頂的數字大就和我們堆頂的數字交換//fsanf的返回值是他讀取到字符個數.while (fscanf(fin, "%d", &count) == 1){if (count > topk[0]){//交換并調整,使它形成新的堆topk[0] = count;AdjustDown(topk, 0, k);}}for (i = 0; i < k; i++){printf("%d ", topk[i]);}fclose(fin);free(topk);
}