[prev] 11 [next]

Insertion with Heaps

Insertion is a two-step process
  • add new element at bottom-most, rightmost position
    (but this might violate heap property; new value larger than parent)
  • reorganise values along path to root to restore heap 

void insert(Heap h, Item it)
{
   assert(h->nitems < h->nslots);
   h->nitems++;
   h->items[h->nitems] = it;
   fixUp(h->items, h->nitems);
}