问题描述:

What should i do to remove a value from min heap when the left and right child are equal and smaller than their parent. For example i have a value 0 on the root of my min heap and want to remove it. I'll swap 0 with the last element of my vector(value=12), after that, i need to run the function that turns the vector into a min-heap again(min-heapfy), but in my example i exchanged 0 with 12, and now 12 is on the root and 0 will be soon returned. I have to swap 12 with the left child(1) or right child(1), how can i know which of this number 1 entered in the vector first?

#include <stdio.h>

#include <stdlib.h>

int left(int i){

return 2*i;

}

int right(int i){

return 2*i +1;

}

void swap_pos(int *vi, int *vm){

int aux;

aux = *vi;

*vi = *vm;

*vm = aux;

}

void heapify(int *v, int i,int heap_size){

int l,r,menor_ind = i;

l = left(i);

r = right(i);

if(l<=heap_size && v[l]<v[i]) menor_ind = l;

if(r<=heap_size && v[r]<v[menor_ind]) menor_ind = r;

if(menor_ind!= i){

swap_pos(&v[i],&v[menor_ind]);

heapify(v,menor_ind,heap_size);

}

}

void build_min_heap(int v[],int heap_size){

int i;

for(i=heap_size/2; i>=1; i--){

heapify(v,i,heap_size);

}

}

int extract(int *v, int *heap_size){

int ret = v[1];

if(*heap_size==0) return -1;// erro

swap_pos(&v[*heap_size],&v[1]); // swap root with the last element

(*heap_size)--;

heapify(v,1,*heap_size);

return ret;

}

void heap_sort(int *v, int *heap_size){

while(*heap_size>=2){

swap_pos(&v[1],&v[*heap_size]);

(*heap_size)--;

heapify(v,1,*heap_size);

}

}

int main(void){

int heap_size = 9;

int i, v[] = {-1,6,12,3,1,5,0,1,9,7};

build_min_heap(v,heap_size);

printf("%d\n",extract(v,&heap_size));

//heap_sort(v,&heap_size);

for(i=1; i<=heap_size; i++){

printf("%d ",v[i]);

}

return 0;

}

网友答案:

As far as the heap goes, 1 and 1 are equal. (Indeed, that is generally true.) So it doesn't matter which 1 becomes the new root. The 12 will percolate up the heap until it finds some place to rest, possibly at the fringe but not necessarily. There's nothing which requires it to get back to where it came from, and it's very likely that it won't.

Why do you think the code you present isn't correct?

相关阅读:
Top