heap / max heap / priority queue

Using array. Could use list as a backing store. All heap-changing operations are O(logn) - occasionally O(n) when list resizes. When top has to be replaced, displace() avoids having to call delete() and insert().

// interface
heap:
    insert(T)     // uses siftup()
    T delete()    // uses siftdown()
    T displace(T) // replaces top, uses siftdown()
    T peek()
    int size()
    int capacity()
    [] foreach()

// max-heap uses array (or list) as a backing store
max-heap: heap
    store
    
    max-heap(capacity)
        if capacity < 0:
            throw
        store = new [capacity]
    
    // add, siftup
    insert(x):
        if isfull():
            throw
        store[count] = x
        count++
        siftup()
    
    // return 0th, [0] = [last], siftdown
    delete():
        if isempty():
            throw
        x = store[0]
        store[0] = store[count-1]
        count--
        siftdown()
        return x
    
    // replace top, siftdown 
    displace(x):
        if isempty():
            throw
        top = store[0]
        store[0] = x
        siftdown()
        return top
    
    peek():
        if isempty():
            throw
        return store[0]
    
    siftup(end = count-1):
        i = end
        while i > 0:
            parent = (i-1) /2
            if store[parent] >= store[i]:
                break
            swap(store, i, parent)
            i = parent
    
    siftdown(start = 0):
        i = start
        while i < count:
            left = i*2 +1
            right = left +1
            max = i
            if left < count && store[left] > store[max]:
                max = left
            if right < count && store[right] > store[max]:
                max = right
            if max == i:
                break
            swap(store, i, max)
            i = max

    //or count()    
    size():
        return count
    isempty():
        return count == 0
    isfull():
        return count == store.length()
    capacity():
        return capacity
    [] foreach():
        for i = 0, i < count, i++:
            yield return store[i]

append(x) is useful in some cases where a delayed call to heapify() is efficient. Heapify() using siftdown() is faster than siftup() as siftdown() only has ~n swaps (0*n/2 + 1*n/4 + 2*n/8 + h*1 = n) i.e O(n) but siftup() has nlogn swaps (h*n/2 + (h-1)*n/4 + (h-2)*n/8... + 2*1 + 0*1) i.e. O(nlogn).

    isheapified = true
    append(x):
        if isfull():
            throw
        store[count] = x
        count++
        isheapified = false
    
    // note: heapify using siftdown is faster
    heapify():
        heapify-siftdown()
        isheapified = true
    // O(n)
    heapify-siftdown():
        start = count/2 -1 // last parent
        while start >= 0:
            siftdown(start)
            start--
    // O(nlogn)
    heapify-siftup():
        end = count-1
        while end > 0:
            siftup(end)
            end--
    
    // delayed call to heapify()
    peek():
        if isempty():
            throw
        if !isheapified:
            heapify()
        return store[0]