5.1 Heap ADT

The ADT of a heap only requires very few interfaces, much like those of a stack or a queue.

• data type

  struct _Heap   {     int *pStorage; // where are nodes stored     unsigned count; // how many nodes do we have   };

• struct Heap *Heap_new(void): allocates and initializes a heap, then returns the pointer to it. A newly created heap should be empty (with no nodes). Furthermore, pStorage should be initialized to NULL.
• void Heap_delete(struct Heap *pHeap): deletes a heap. If the heap is still attached to an array, do not delete the array!
• void Heap_attach(struct Heap *pHeap, int *pStorage): the storage of a heap is now associated with a given address.
• int Heap_isempty(struct Heap *pHeap): returns 1 iff the heap pointed to by pHeap has at least one node.
• void Heap_insert(struct Heap *pHeap, int v): inserts a new node with the value v into the heap pointed to by pHeap.
• int Heap_remove(struct Heap *pHeap): removes the root of the heap pointed to by pHeap, and returns its value. The heap should be maintained.

Special care should be taken so that if a heap only has n items, then it should only use sizoef(int) ∗ n bytes, starting from the location pointed to by pStorage. This involves shifting all serial numbers by one so that the root has a serial number of 0 (instead of 1).