Build

Creating a min-max heap is accomplished by an adaptation of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion.^[4] A typical Floyd's build-heap algorithm^[6] goes as follows:

function FLOYD-BUILD-HEAP(h):
    for each index i from ${\displaystyle \lfloor length(h)/2\rfloor }$down to 1 do:
        push-down(h, i)
    return h

In this function, h is the initial array, whose elements may not be ordered according to the min-max heap property. The push-down operation (which sometimes is also called heapify) of a min-max heap is explained next.

Push Down

The push-down algorithm (or trickle-down as it is called in ^[4] ) is as follows:

function PUSH-DOWN(h, i):
    if i is on a min level then:
        PUSH-DOWN-MIN(h, i)
    else:
        PUSH-DOWN-MAX(h, i)
    endif

function PUSH-DOWN-MIN(h, i):
    if i has children then:
        m := index of the smallest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if h[m] > h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] < h[i] then:
            swap h[m] and h[i]
        endif 
    endif

function PUSH-DOWN-MAX(h, i):
    if i has children then:
        m := index of the largest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if h[m] < h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] > h[i] then:
            swap h[m] and h[i]
        endif 
    endif

function PUSH-DOWN-ITER(h, m):
    while m has children then:
        i := m
        if i is on a min level then:
            m := index of the smallest child or grandchild of i
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] > h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        else:
            m := index of the largest child or grandchild of i
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] < h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        endif
    endwhile

Insertion

To add an element to a min-max heap perform following operations:

1. Append the required key to (the end of) the array representing the min-max heap. This will likely break the min-max heap properties, therefore we need to adjust the heap.
2. Compare the new key to its parent:
   1. If it is found to be less (greater) than the parent, then it is surely less (greater) than all other nodes on max (min) levels that are on the path to the root of heap. Now, just check for nodes on min (max) levels.
   2. The path from the new node to the root (considering only min (max) levels) should be in a descending (ascending) order as it was before the insertion. So, we need to make a binary insertion of the new node into this sequence. Technically it is simpler to swap the new node with its parent while the parent is greater (less).

This process is implemented by calling the push-up algorithm described below on the index of the newly-appended key.

Push Up

The push-up algorithm (or bubble-up as it is called in ^[7] ) is as follows:

function PUSH-UP(h, i):
    if i is not the root then:
        if i is on a min level then:
            if h[i] > h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MAX(h, parent(i))
            else:
                PUSH-UP-MIN(h, i)
            endif
        else:
            if h[i] < h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MIN(h, parent(i))
            else:
                PUSH-UP-MAX(h, i)
            endif
        endif
    endif

function PUSH-UP-MIN(h, i):
    if i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MIN(h, grandparent(i))
    endif

function PUSH-UP-MAX(h, i):
    if i has a grandparent and h[i] > h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MAX(h, grandparent(i))
    endif

function PUSH-UP-MIN-ITER(h, i):
    while i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        i := grandparent(i)
    endwhile

Find Minimum

The minimum node (or a minimum node in the case of duplicate keys) of a Min-Max Heap is always located at the root. Find Minimum is thus a trivial constant time operation which simply returns the roots.

Find Maximum

The maximum node (or a maximum node in the case of duplicate keys) of a Min-Max Heap that contains more than one node is always located on the first max level--i.e., as one of the immediate children of the root. Find Maximum thus requires at most one comparison, to determine which of the two children of the root is larger, and as such is also a constant time operation. If the Min-Max heap containd one node then that node is the maximum node.

Remove Minimum

Removing the minimum is just a special case of removing an arbitrary node whose index in the array is known. In this case, the last element of the array is removed (reducing the length of the array) and used to replace the root, at the head of the array. push-down is then called on the root index to restore the heap property in ${\displaystyle O(\log _{2}(n))}$time.

Remove Maximum

Removing the maximum is again a special case of removing an arbitrary node with known index. As in the Find Maximum operation, a single comparison is required to identify the maximal child of the root, after which it is replaced with the final element of the array and push-down is then called on the index of the replaced maximum to restore the heap property.