The keys in a binary heap are according to the heap-order property. Suppose that

Question

 The keys in a binary heap are according to the heap-order property. Suppose that they are scrambled. Write a program FixHeap.java fixing the heap. Use the array representation of the heap. The keys should be provided in a string as the input (so that TA can run it as  "java FixHeap string"). Implement 3 ways of fixing the heap and compute the number of swaps in each (3 numbers).   1) Fixing the heap. Repeat the following step: find the two nodes with indices i and j such that Heap[i] and Heap[j] are not in heap-order and j is maximum, then swap them. Fix the heap and count the number of swaps.  2) Fix the heap by constructing it. Take the input sequence of numbers and insert them into an empty heap. Count the total number of swaps in all insertions.   3) Construction of the heap by merging. Use the algorithm with O(n) running time (using downheap to restore the heap-order property).  Count the total number of swaps. 

Explanation / Answer

public class heap_Sort{
  public static void main(String a[]){
  int i;
  int arr[] = {1,3,4,5,2};

  System.out.println("   Heap Sort --------------- ");
  System.out.println("   Unsorted Array ");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  for(i=arr.length; i>1; i--){
  fnSortHeap(arr, i - 1);
  }
  System.out.println("   Sorted array --------------- ");
  for (i = 0; i < arr.length; i++)
  System.out.print(" "+arr[i]);
  }

  public static void fnSortHeap(int array[], int arr_ubound){
  int i, o;
  int lChild, rChild, mChild, root, temp;
  root = (arr_ubound-1)/2;

  for(o = root; o >= 0; o--){
  for(i=root;i>=0;i--){
  lChild = (2*i)+1;
  rChild = (2*i)+2;
  if((lChild <= arr_ubound) && (rChild <= arr_ubound)){
  if(array[rChild] >= array[lChild])
  mChild = rChild;
  else
  mChild = lChild;
  }
  else{
  if(rChild > arr_ubound)
  mChild = lChild;
  else
  mChild = rChild;
  }

  if(array[i] < array[mChild]){
  temp = array[i];
  array[i] = array[mChild];
  array[mChild] = temp;
  }
  }
  }
  temp = array[0];
  array[0] = array[arr_ubound];
  array[arr_ubound] = temp;
  return;
  }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.