#include <stdio.h>
#include <stdlib.h>
#define n 10
void swap(int * a , int * b);
int parent(int i){
return ((i+1)/2)-1;
}
int left(int i){
return 2*(i+1)-1;
}
int right(int i){
return (2*(i+1)+1)-1;
}
int printHeap(int *heap, int pos){
int i;
for (i=0;i<pos;i++){
printf("%d ",heap[i]);
}
printf("----\n");
}
int insert(int *heap,int *pos, int value)
{
int i=*pos;
int tmp;
heap[i]=value;
(*pos)++;
while(parent(i)>=0) {
if(heap[parent(i)]<heap[i]){
tmp=heap[parent(i)];
heap[parent(i)]=heap[i];
heap[i]=tmp;
}else{
break;
}
i=parent(i);
}
}
void deleteMax(int *heap,int *pos)
{
int tmp;
heap[0]=heap[*pos-1];
(*pos)--;
maxHeapify(heap,&pos);
}
void maxHeapify(int *heap,int *pos)
{
int i=*pos,l=left(i),r=right(i),max;
if (l<i && heap[l]>heap[i])
max=l;
else
max=i;
if(r<i && heap[r]>heap[max])
max=r;
if (max!=i)
{
swap(&heap[i],&heap[max]);
maxHeapify(heap,max);
}
}
void swap(int * a , int * b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
int main()
{
int heap[n];
int pos=0;
insert(heap,&pos, 10);
insert(heap,&pos, 5);
insert(heap,&pos, 15);
insert(heap,&pos, 35);
insert(heap,&pos, 66);
insert(heap,&pos, 41);
insert(heap,&pos, 42);
insert(heap,&pos, 21);
insert(heap,&pos, 14);
insert(heap,&pos, 3);
printHeap(heap,pos);
deleteMax(heap,&pos);
printHeap(heap,pos);
system("PAUSE");
return 0;
}
我有这个堆实现,我想删除最大堆(heap [0]),然后修复整个数组,首先用最后一个元素(min)替换最大堆,然后尝试使用maxHeapify修复结构方法,但我似乎出了点问题,知道吗?先感谢您!
最佳答案
您需要将maxHeapify放入这样的循环中:
void BuildMaxHeap(int* arr)
{
for( int i = 9; i >= 0; i-- )
maxHeapify( arr, &i );
}
void maxHeapify( int* arr, int *pos )
{
int i = *pos;
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if( left < n && arr[ left ] > arr[ largest ] )
largest = left;
if( right < n && arr[ right ] > arr[ largest ] )
largest = right;
if( largest != i )
{
int temp = arr[ i ];
arr[ i ] = arr[ largest ];
arr[ largest ] = temp;
maxHeapify( arr, &largest );
}
}
关于c - 删除最大堆方法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23980215/