CODEWITHSUNDEEP
javaalgorithmsortingheap
Hopeless Programmer
Hopeless Programmer

Reputation: 267

Minimum Heap Algorithm

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?

Upvotes: 1

Views: 1922

Answers (3)

Salman Paracha
Salman Paracha

Reputation: 1703

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.

Upvotes: 0

Shraddha
Shraddha

Reputation: 2335

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

Upvotes: 3

Marsellus Wallace
Marsellus Wallace

Reputation: 18611

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)?

Upvotes: 0

Related Questions