堆
是一種完全二叉樹，分為大堆，小堆
如果有一個關(guān)鍵碼的集合 int K[ ] = {27,15,19,18,28,34,65,49,25,37} ; 把它的所有元素按完全二叉樹的順序存儲方式存儲
在一個一維數(shù)組中，并滿足：Ki <=K2*i+1 且Ki <=K2*i+2 ( Ki >=K2*i+1 且Ki >=K2*i+2) i = 0，1，
2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
- 堆總是一棵完全二叉樹。
建堆的方式
有兩種，1.向上建堆，2.向下建堆
向上建堆
時間復(fù)雜度為：O(N*logN)
typedef int HPDataType;
//交換函數(shù)
void Swap(HPDataType* a, HPDataType* b) {
HPDataType temp = *a;
*a = *b;
*b = temp;
}
//向上調(diào)整的條件是：調(diào)整的child結(jié)點之前的結(jié)點應(yīng)該也為大堆/小堆，所以，向上調(diào)整建堆的時候，是從數(shù)組的第一個元素開始
void ADjustUp(HPDataType* a, int child) {
//向上調(diào)整
int parent = (child - 1)/2;
while (child >0) //child!=0
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);//取地址進行交換
//進行交換
child = parent;
parent = (child - 1) /2;
}
else {
break;
}
}
}
//向上建堆
//for (int i = 0; i < n; i++) {
// ADjustUp(arr, i);
//}
int main(){
int arr[]={23,23,1,32,12,3,12,31,324};
int n=sizeof(arr)/sizeof(arr[0]);//得到數(shù)組的個數(shù)大小
//n-1表示為數(shù)組最后一個元素的下標，（n-1-1）/2得到其父節(jié)點，從父結(jié)點開始，向下調(diào)整
for (int i = 0; i < n; i++) {
ADjustUp(arr, i);
}
}
向下建堆
時間復(fù)雜堆為：O(N)
typedef int HPDataType;
//交換函數(shù)
void Swap(HPDataType* a, HPDataType* b) {
HPDataType temp = *a;
*a = *b;
*b = temp;
}
//向下調(diào)整建堆的條件為：左右子樹都為大堆/小堆，所以從最后一個結(jié)點開始，又因為如果是葉子結(jié)點的話，本身調(diào)整是沒有意義的，所以就從倒數(shù)第二層開始
void AdjustDown(HPDataType* a, int n, int parent) {
int child = parent * 2 + 1;//先找到左孩子的位置
while (child < n) {
//從左右孩子里面選一個
if (child + 1 < n && a[child + 1] > a[child]) {
//如果右孩子存在，且，右孩子大于左孩子
child++;//
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
//向下建堆
int main(){
int arr[]={23,23,1,32,12,3,12,31,324};
int n=sizeof(arr)/sizeof(arr[0]);//得到數(shù)組的個數(shù)大小
//n-1表示為數(shù)組最后一個元素的下標，（n-1-1）/2得到其父節(jié)點，從父結(jié)點開始，向下調(diào)整
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(arr, n, i);
}
}
計算兩種方式的時間復(fù)雜度
我們可以看到的是向下調(diào)整建堆時間復(fù)雜度更小，我們通過每一層的每一個結(jié)點的最多需要調(diào)整的次數(shù)為依據(jù)，假設(shè)高度為h，如果是向上調(diào)整的話，最后一個結(jié)點（最后一層，也就是2^(h-1)個結(jié)點），最多調(diào)整h-1次，向上的時候需要調(diào)整的每一層結(jié)點變少，層數(shù)變少，所以最后肯定是總調(diào)整次數(shù)更多
如圖所示：這個圖可以從數(shù)學的角度上來解決這個問題
堆排序
采用向上或者是向下調(diào)整的方法，最后實現(xiàn)排序，最后的時間復(fù)雜度為：O(N*logN)
//所以不管是向上還是向下建堆，時間復(fù)雜度都是為O(N*logN)
void HeapSort(int arr[],int n){
//比較偏向于向下調(diào)整建堆 時間復(fù)雜度：O(N)
for(int i=(n-1-1)/2;i>=0;i--){
AdjustDown(arr,n,i);
}
//向上建堆，時間復(fù)雜度為 O(N*logN)
//for (int i = 0; i < n; i++) {
// ADjustUp(arr, i);
//}
//進行排序,如果想要升序，那就建大堆，然后進行向下調(diào)整
int end = n - 1;//從最后一個結(jié)點開始
while (end>0) {
Swap(&arr[end], &arr[0]);
AdjustDown(arr, end, 0);//向下調(diào)整
end--;
}
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
int main()
{
int arr[]={2,231,2,3,12,312,3,123,423,4,2};
int n=sizeof(arr)/sizeof(arr[0]);
HeapSort(arr,n);
return0;
}
Top-K問題
Top-K問題：從N個數(shù)據(jù)中找出前k個最大/最小的數(shù)
當然，在N的數(shù)值不是很大的時候，我們可以使用堆排序的方法，找到對應(yīng)的前k個數(shù)值，但是當N的個數(shù)為10億，或者是100億的時候，這個數(shù)據(jù)的處理量就不能用原本的簡單的堆排序方法啦
思路如下
假如說是100億個數(shù)據(jù)量，我們由以下的內(nèi)存換算可知，100億個整數(shù)的數(shù)據(jù)量就是將近40G，所以不能單純用簡單的堆排序來運算
新的思路如下：
- 建立一個大小為k的數(shù)組，將前k個數(shù)值建成一個小堆
- 最后遍歷剩余的數(shù)值，對于每一個數(shù)值，都進行向下調(diào)整（如果是這個數(shù)值大于頂部結(jié)點，就代替他，并進行向下調(diào)整）
- 最后這個小堆的數(shù)據(jù)就是最大的前k個
void AdjustDown(int* a, int n,int parent) {
int child = parent * 2 + 1;//先找到左孩子
while (child < n) {//對于小堆的向下調(diào)整
if (child + 1 < n && a[child + 1] < a[child]) {
//如果右孩子大于左孩子，那么就進行交換
child++;
}
if (a[child] < a[parent]) {
int temp = a[child];
a[child] = a[parent];
a[parent] = temp;
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void PrintTopK(const char*file,int k){
//輸出前k個數(shù)值
//1.我們先創(chuàng)建為k個數(shù)據(jù)的小堆
int*topK=(int*)malloc(sizeof(int)*k);
assert(topK);
FILE*fout=fopen(file,"r");//讀取文件 file
if(fout==NULL){
perror("open fail");
return;
}
//讀取前k個數(shù)值做小堆
for(int i=0;i<k;i++){
fscanf(fout,"%d",&topK[i]);//讀取前k個數(shù)值在數(shù)組topK中
}
for(int i=(k-2)/2;i>=0;i--){
AdjustDown(topK,k,i);//將topK數(shù)組建立小堆
}
//2.將剩余的n-k個元素依次于對頂元素進行交換，不滿則替換
int val=0;
int ret=fscanf(fout,"%d",&val);
while(ret!=EOF){//如果文件中的數(shù)值全部被讀取，那么就會返回EOF
if(val>topK[0]){
topK[0]=val;//直接賦值即可，不必要交換
AdjustDown(topK,k,0);//向下調(diào)整
}
ret=fscanf(fout,"%d",&val);
}
for(int i=0;i<k;i++){
printf("%d",topK[i]);//打印topK數(shù)組中k個數(shù)值，這就是文件中n個數(shù)值中最大的前k個數(shù)
}
print("\n");
free(topK);
fclose(fout);
}
void CreateNData(){
//創(chuàng)建N個數(shù)據(jù)
int n=1000000;
srand(time(0));//使用隨機數(shù)前要i使用這個代碼
const char*file="data.txt";
FILE*fin=fopen(file,"w");
if(fin==NULL){
perror("fopen fail");
return;
}
for(int i=0;i<n;i++){
int x=rand()%10000;
fprintf(fin,"%d\n",x);//讀寫n個數(shù)據(jù)在fin所對應(yīng)的“data.txt”文件中
}
fclose(fin);//關(guān)閉文件，這樣才能正確的在硬盤文件中“data.txt”存儲數(shù)值
}
int main()
{
CreateNData();
PrintTopK("data.txt",10);//表示從文件data.txt中讀取前10個最大的數(shù)值
return 0;
}
實驗結(jié)果如下：成功讀取出來1000000隨機數(shù)中前k個最大的數(shù)字
文章來源：http://www.zghlxwxcb.cn/news/detail-407961.html
本文主要是對于堆的定義，堆的兩種創(chuàng)建方式，向上建堆和向下建堆，進行代碼演示，并對其分析時間復(fù)雜度，且實現(xiàn)了堆排序，實際上堆排序就是先建立堆（向上向下都可，建議向下），然后使用while循環(huán)，循環(huán)n-1次對于頭尾進行交換，然后進行向下調(diào)整，上文有詳解，最后是對于Top-K堆問題的解釋，并附上代碼進行演示文章來源地址http://www.zghlxwxcb.cn/news/detail-407961.html
到了這里，關(guān)于堆（兩種建堆方法）、堆排序和Top-K問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
