Data Structure Heap Algorithms MCA Sem 2

Data Structure Algorithm for  Heap Operations  pseudo-code.

After knowing and completely understanding this algorithm for  Heap Operations . You will be able to write a Data Structure Programs for  Heap Operations  in any language. The basic ideology and idea behind all the programs will be same. Yes the programs will differ according to the syntax and semantics of the language. This is a part of Mumbai University MCA Colleges Data Structure MCA Sem 2

ReheapUp:-

Algorithm ReheapUp(heap, newNode)

1 if(newNode <> 0) (* if not root of heap *)

1 parent := (newNode-1)/2

2 if (heap[newNode]>heap[parent]) (* child greater than parent *)

1 hold = heap[parent]

2 heap[parent] = heap[newNode] (* exchange *)

3 heap[newNode] = hold

4 ReheapUp (heap, parent) (*continue reheapUP *)

3 end if

2 end if

End ReheapUp

Heap Insertion:-

Algorithm InsertHeap(heap, last, data) : BOOLEAN

1 if (last = HeapSize -1)

1 return FALSE (* over the heap size limitation *)

2 increment last (* increase the size of the heap *)

3 heap[last] = data (* put the data at the last position *)

4 ReheapUp(heap, last) (* restore the heap *)

5 return TRUE

End InsertHeap

ReheapDown:-

Algorithm ReheapDown (heap, root, last)

1 if ((root*2 +1) <= last) (* There is at least left child *)

2 leftKey := heap[root*2 +1] (* left child value *)

3 rightChild := FALSE (* assume no right child)

1 if ((root*2 + 2) <= last) (* There is also right child *)

1 rightKey := heap[root*2 +2] (* right child value *)

2 rightChild := TRUE

2 end if

3 largeChildKey := leftKey;

4 largeChildIndex := root*2 + 1; (* assume left child larger *)

5 if (rightChild AND leftKey < rightKey)

1 largeChildKey := rightKey; (* right child exists and is larger *)

2 largeChildIndex := root*2 +2;

6 end if

7 if (heap[root] < largeChildKey) (* exchange larger child with root *)

1 hold := heap[root];

2 heap[root] := heap[largeChildIndex];

3 heap[largeChildIndex] := hold;

4 reheapDown (heap, largeChildIndex, last);

8 end if

2 end if

end ReheapDown

Heap Deletetion

Algorithm DeleteHeap(heap, last, dataOut)

1 if (last < 0) (* empty heap *)

1 return FALSE

2 dataOut := heap[0] (* remove the largest data at root *)

3 heap[0] := heap[last] (* restore the shape *)

4 decrement last

5 reheapDown (heap, 0, last) (* restore the order property *)

6 return TRUE

End DeleteHeap

Algorithm for converting to max heap:-

Algorithm CreateHeap(list)

1 set index to 1

2 loop (index <= listLength)

1 reheapUp(list, index)

2 increment index

3 end loop

End CreateHeap

Heap Sort Algorithm:-

Algorithm HeapSort(list, last)

(* Create a heap *)

1 CreateHeap(list)

2 sorted := last;

3 loop (sorted > 0)

1 holdData := list[0] (* exchange 0 and sorted *)

2 list[0] := list[sorted]

3 list[sorted] = holdData

4 decrement sorted

5 reheapDown (list, 0, sorted);

4 end loop

End HeapSort


Hope this Algorithm is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.