Minimum Heap Algorithm

Question

This is my minHeap algorithm however it doesn't function as expected:

public static int [] fixheap(int heap[], int n, int i){
    int j=2*i;
    int weight = heap[i];

    while (j<=n){
        if((j<n) && heap[j] > heap[j+1])
            j++;
        if(weight <= heap[j]) break;
        else 
        heap[j/2] = heap[j]; 

        j=j*2;
    }

    heap[j/2]= weight;

    return heap;
}

public static void makeheap(int heap[], int n){

    for (int i=n/2; i>=0; i--){
        fixheap(heap, n ,i);
    }   
}

When the data elements are added in various orders the algorithm returns incorrect minHeaps. Can anyone see any apparent problems for this minimum heap algorithm?

please make sure to accept an answer that is appropriate.

Salman Paracha
– Salman Paracha

2012-01-18 02:41:27 +00:00
Commented Jan 18, 2012 at 2:41 — Salman Paracha
– Salman Paracha, Commented Jan 18, 2012 at 2:41

Shraddha · Accepted Answer · 2012-01-17 20:41:45Z

3

You are comparing the wrong elements of the array for forming the heap. Try to dry run your program

As the array starts from the index 0, you should take i=n/2-1 initially here.

public static void makeheap(int heap[], int n){

     for (int i=n/2 - 1; i>=0; i--){
     fixheap(heap, n ,i);
    }   
}

And then you will have to change your fixheap function to get the correct value for j

j = i*2 + 1

edited Jan 17, 2012 at 20:41

answered Jan 17, 2012 at 20:34

Shraddha

2,3351 gold badge16 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marsellus Wallace · Accepted Answer · 2012-01-17 20:36:00Z

0

I believe that the way you find the parent and/or the children is incorrect.

Think about it, if the left children is at index1 and the right at index2, how do I get to their parents at index0?

What about finding index0's children (index1 and index2)?

answered Jan 17, 2012 at 20:36

Marsellus Wallace

18.7k28 gold badges96 silver badges160 bronze badges

Comments

Salman Paracha · Accepted Answer · 2012-01-17 21:05:07Z

The folllwing code is in python, but I will highlight the lines that do the heavy lifting, and in the process hopefully present a different solution of creating a min-heap

heapArray = []  
for heapKey in someArray:
    insert(heapArray, int(heapKey))
return heapArray;

def insert(heapArray, heapKey):
  heapArray.append(heapKey)
  index_of_key = len(heapArray)-1
  parent_index_of_key = (index_of_heap_key-1)/2
  while index_of_key>0:
    if(heapKey < heapArray[parent_index_of_key]):
        __swap(index_of_key, parent_index_of_key, heapArray)
        index_of_key = parent_index_of_key;
        parent_index_of_key = (index_of_key-1)/2
    else:
        break # we have reached the right spot

In the above example, we re-create the heap (yes that means more memory, but for illustration purposes this maybe a good start). As we create the heap, we simply check the value of the newly inserted key with its parent (via parent_index_of_key).

If the parent is larger than its child, then we swap the value and update the indexes (both for the swapped key and its new parent). We repeat that process until we have either reached the top of the heap or if the heap key can't go any further up the chain

The in-place swaps are clearly more efficient, but the above is more intuitive and easy to follow. Clearly, I won't use the above code, where memory is a large constraint, but would consider it for cases where code conciseness and clarity trump memory utilization.

Collectives™ on Stack Overflow

Minimum Heap Algorithm

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related