Binary Heap

The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest.

ADT of Heap

Structure MAXHEAP is

  MaxHeap Create(max_size)      ::=  create an empty heap that can hold a

                                                     maximum of max_size element.

  Boolean HeapFull(heap,n)        ::=  if(n==max_size)return TRUE else

                                                     return FALSE

  MaxHeap Insert(heap,item,n)   ::=  if(!HeapFull(heap,n) insert item into

                                                     heap and return the resulting heap

                                                     else return error.

  Boolean HeapEmpty(heap,n)    ::=  if(n=0)return TRUE else return

                                                     FALSE

  Element Delete(heap,n)           ::=  if(!HeapEmpty(heap,n)return one

                                                     instance of the largest element in the

                                                     heap and remove it from the heap

                                                     else return error.