手打小顶堆,其中一个写法有错。求助大佬
查看原帖
手打小顶堆,其中一个写法有错。求助大佬
389268
LeM0NAdE楼主2021/8/18 20:29

这是我的代码,大佬们帮忙看看down函数就行。没有注释掉的down函数不能AC,加注释的可以AC,帮帮蒟蒻吧。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int size;//记录当前堆中的元素个数
void swap(int *a,int *b){
    int temp=*a;
    *a = *b,*b=temp;
}
void up(int now,int *heapmin)
{
    while(now>1){
        if(heapmin[now]<heapmin[now/2]){
            swap(&heapmin[now],&heapmin[now/2]);
            now/=2;
        }
        else{
            break;
        }
    }
}
void insert(int val,int *heapmin)
{
    heapmin[++size]=val;
    up(size,heapmin);//由底向顶调整
}

void down(int *heapmin){
    int tmp=1;
    while(tmp<=(size/2)){
        if(heapmin[tmp<<1]>heapmin[tmp<<1|1]&&(tmp*2+1<=size)){
            swap(&heapmin[tmp<<1],&heapmin[tmp<<1|1]);
        }
        if(heapmin[tmp]>heapmin[tmp<<1]){
            swap(&heapmin[tmp],&heapmin[tmp<<1]);
            tmp=tmp<<1;
        }
        else{
            break;
        }
    }
}/*
void down(int p,int *heap) //二叉小根堆向下调整
{
  int s=p*2;
  while(s<=size)
  { //下面这句话是从左右儿子中选一个更小的做交换
    if(s<size&&heap[s+1]<heap[s]) s++;
    if(heap[s]<heap[p])
    {
      swap(&heap[s],&heap[p]);
      p=s; s=p*2;
    }
    else break;
  }
}*/
void extract(int *heapmin)//小顶堆删除堆顶
{
    heapmin[1]=heapmin[size--];
    down(heapmin);
}
int main()
{
    int n,i,ans=0;
    scanf("%d",&n);
    int heapmin[100009];//小根堆
    for(i=1;i<=n;i++)
    {
       int tmp;
       scanf("%d",&tmp);
       insert(tmp,heapmin);
    }
    for(i=1;i<n;i++)
    {
        int x=heapmin[1];
        extract(heapmin);
        int y=heapmin[1];
        extract(heapmin);
        ans+=x+y;
        insert(x+y,heapmin);
    }
    printf("%d",ans);
    return 0;
}

2021/8/18 20:29
加载中...