java - Heapify function not working -

java - Heapify function not working -

i have been trying write recursive heapify method turns array of integers min-heap. main , heap classes shown below. of array shown in main min-heap, subtree [11, 4, 5] not min-heap. however, heapify function doesn't seem reach subtree. can't figure out problem is, help appreciated.

public class heap { public heap(int[] array) { heap = array; } public void heapify() { heapifyhelper(0); } public void heapifyhelper(int rootindex) { if(isleafindex(rootindex)) { return; } else { int leftchildindex = getleftchildindex(rootindex); int rightchildindex = getrightchildindex(rootindex); int leftchildvalue = heap[leftchildindex]; int rightchildvalue = heap[rightchildindex]; int rootvalue = heap[rootindex]; if(leftchildvalue < rootvalue && leftchildvalue < rightchildvalue) { swap(rootindex, leftchildindex); heapifyhelper(leftchildindex); heapifyhelper(rightchildindex); } else if(rightchildvalue < rootvalue && rightchildvalue < leftchildvalue) { swap(rootindex, rightchildindex); heapifyhelper(leftchildindex); heapifyhelper(rightchildindex); } } } public int getleftchildindex(int parentindex) { homecoming 2 * parentindex + 1; } public int getrightchildindex(int parentindex) { homecoming 2 * parentindex + 2; } public int getparentindex(int childindex) { if(childindex == 0) { throw new illegalargumentexception("cannot parent index of root."); } else { homecoming (childindex / 2) - 1; } } public boolean isleafindex(int index) { int leftindex = getleftchildindex(index); int rightindex = getrightchildindex(index); if(leftindex >= heap.length && rightindex >= heap.length) { homecoming true; } else { homecoming false; } } public void swap(int index1, int index2) { int temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } public void printheap() { system.out.println(arrays.tostring(heap)); } int[] heap; } public class main { public static void main(string[] args) { int[] x = {0, 5, 2, 9, 11, 6, 12, 21, 32, 4, 5}; heap heap = new heap(x); heap.printheap(); heap.heapify(); heap.printheap(); } }

there several problems in heapifyhelper:

public void heapifyhelper(int rootindex) { if(isleafindex(rootindex)) { return; } else { int leftchildindex = getleftchildindex(rootindex); int rightchildindex = getrightchildindex(rootindex); int leftchildvalue = heap[leftchildindex]; int rightchildvalue = heap[rightchildindex];

what if leftchildindex == heap.length - 1? rightchildvalue cause arrayindexoutofboundsexception.

int rootvalue = heap[rootindex]; if(leftchildvalue < rootvalue && leftchildvalue < rightchildvalue) { swap(rootindex, leftchildindex); heapifyhelper(leftchildindex); heapifyhelper(rightchildindex); } else if(rightchildvalue < rootvalue && rightchildvalue < leftchildvalue) {

what if both children equal, , smaller parent? in case don't swap @ all.

swap(rootindex, rightchildindex); heapifyhelper(leftchildindex); heapifyhelper(rightchildindex); } } }

and reason why subtree [11, 4, 5] isn't reached because phone call heapifyhelper children if 1 of children smaller parent, when phone call heapifyhelper(1), 2 children of node 5 9 , 11, both larger root value. (actually, don't phone call heapifyhelper(1), since heap[0]is smaller both children.)

but rectifying lone unconditionally recurring (on children exist) doesn't create heapify correct. if recur root leaves, each value can bubble @ 1 level. must recur leaves root(1), , need sift values downwards completely, not 1 level.

if swap value 1 of children, each position considered @ twice. 1 time when comparing parent, 1 time when comparing children. when go root leaves, when compare position children, no position above (no position smaller index, even) can ever changed anymore.

so each value can bubble @ 1 level. if smallest element below direct children of root, root won't become smallest element in tree. if start leaves (or rather parents of leaves), values can bubble far need. if swap value smaller of children (if smaller value), each value can still bubble downwards 1 level, still need not create heap.

let consider tree

7 / \ / \ 2 6 / \ / \ 1 3 4 5

if go root leaves, swap 2 , 7 first, giving

2 / \ / \ 7 6 / \ / \ 1 3 4 5

the top 2 levels min-heap.

then treat left subtree, , right subtree, producing

2 / \ / \ 1 4 / \ / \ 7 3 6 5

altogether. bottom 2 levels composed of min-heaps, heap property destroyed in level above. create heap again, 1 must sifted farther (in case, 1 level).

if go leaves root, first treat right subtree,

6 / \ 4 5

producing

4 / \ 6 5

for that, left subtree

2 / \ 1 3

producing

1 / \ 2 3

there. both subtrees min-heaps. altogether, have

7 / \ / \ 1 4 / \ / \ 2 3 6 5

then you'd swap 7 , 1, producing

1 / \ / \ 7 4 / \ / \ 2 3 6 5

now root smallest value, lastly swap destroyed heap property of left subtree. create heap again, 7 must sifted downwards further.

so need siftdown method (and/or siftup method) sifts value downwards (up) far needed.

private void siftdown(int index) { int leftchildindex = getleftchildindex(index); if (leftchildindex >= heap.length) { // leaf, no farther sifting downwards possible return; } int rightchildindex = getrightchildindex(index); if ((heap[leftchildindex] < heap[index]) && (rightchildindex >= heap.length || heap[rightchildindex] >= heap[leftchildindex)) { // left kid smallest or only, , smaller parent swap(index, leftchildindex); siftdown(leftchildindex); } else // left kid not smaller parent, or right kid exists , smaller parent if (rightchildindex < heap.length && heap[rightchildindex] < heap[index]) { swap(index, rightchildindex); siftdown(rightchildindex); } // otherwise, 1 has no smaller child, no more sifting needed }

then right heapify be

public void heapify() { // lastly index has child: int lastnonleafindex = heap.length/2 - 1; for(int index = lastnonleafindex; index >= 0; --index) { siftdown(index); } }

that works because if have (binary) tree both of subtrees min-heaps, sifting downwards root value constructs min-heap:

if root value smaller (or equal to) both children, entire tree min-heap. otherwise, after root value has been swapped smaller of children (without loss of generality left), other subtree unchanged, hence still min-heap. and, since left kid smallest value in left subtree before swap, value @ root smallest value in entire tree after swap. swapping may have destroyed min-heap property of left child, though. left-left , left-right subtrees have not been changed, still min-heaps. , new left subtree smaller original tree, induction hypothesis, sifting downwards root value creates min-heap that. after sifting downwards has finished, have tree smallest value @ root, both of subtrees min-heaps, is, min-heap.

since each leaf trivially min-heap, each index processed in heapify, subtree rooted @ index becomes min-heap.

the alternative, using siftup:

private void siftup(int index) { if (index == 0) return; // root, nil int parentindex = getparentindex(index); // see note below if (heap[index] < heap[parentindex]) { swap(index, parentindex); siftup(parentindex); } } public void heapify() { for(int index = 1; index < heap.length; ++index) { siftup(index); } }

the code siftup much shorter siftdown, since 2 nodes involved here, , there no need check whether kid index falls outside array. heapify less efficient (see footnote (1)).

siftup method used insert new value heap. 1 builds heap inserting values (except root value) existing min-heap [when siftup(index) called, part of array before index min-heap].

note: getparentindex incorrect,

return (childindex / 2) - 1;

says parent of index 1 -1, , parent of index 3 0, right is

return (childindex - 1) / 2;

(1) actually, can proceed root leaves, if sift each value far needed. it's more efficient heapify going [parents of the] leaves root. if go root leaves, @ level k have 2^k values may need bubble k levels, gives o(n*log n) complexity building heap. if proceed [parents of the] leaves upward, have 2^(log n - 1 - k) values may need bubble downwards k levels, gives complexity of o(n) building heap.

java data-structures heap