问题描述:

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?

您可能感兴趣的文章：

- java - Checking user input is a number
- javascript - How to set mobile number validation on my jsp page?
- c++ - 3DTexture-based Volume Rendering
- web - Constructors and Subproperties in Javascript
- asp.net mvc - Exposing Large Data Models via OData and WebAPI
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial