heap operations

Add and remove operations for heaps are in logarithmic time, which are quite efficient.

These are clean and orderly data structures because they are backed by arrays.

Heaps have an edge for simplicity in comparison to BST and the various variants thereof.

Adding and removing in heaps

Heaps are not designed for searching or accessing arbitrary data. Therefore we only care about the add and remove operations.

• The shape property must be maintained first prior to working on order
• The order property is naturally handled once the shape is correctly maintained

Adding to a heap

We start by putting data in the array such that the shape is not destroyed

• This is typically accomplished by just adding to the end of the heap or next available spot in the array
  • We can ensure completeness in the structure
• Once the shape is maintained we can enforce the order property
  • Up-heap starting from the new data to fix the order property
    • Compare the data to the parent ("heapify") by swapping nodes if the order does not match
    • Until the child has the proper relationship with the parent we will continue to swap and traverse up the tree
    • This ensures the order property is maintained by swapping data placement with incorrect orders
• The time complexity for adding to the heap is O(logn)

Remove from a heap

Removing data from the array is similar to the add method.

• Remove from the root
• Down-heap, move the last element of the heap to replace the root
• Once the shape is maintained we can enforce the order property
  • Down-heap the data starting from the new replacement root (index size)
  • Traverse the heap comparing the nodes together
  • Cases:
    • If two children, compare data with higher priority child
    • If one child (must be left), compare data with the child
    • If no children, method terminates
    • Swap if necessary based on comparison
    • Continue down the heap until no swap is made or a leaf is reached
• The time complexity for removing from a heap is O(logn)

Potential use case examples

Below are a few use cases. In particular, the union reminds me quite a bit of the SQL Server implementations that we notice in query plans.

Union

A union operation is defined as taking two valid heaps of the same type (min or max) and fusing them together into one larger heap.

This can be useful for combining two different existing data sets for analysis.

Another example is a subroutine in other algorithms that stratify the data to learn more local information before combining it later.

Increase priority

This is explanatory from the name, taking an item in the heap and boosting the priority level. This would be like patients in an emergency roomt.

The operation is difficult because finding the item may take time.

• Note: The union and increase priority operations are useful but a binary heap is poor at executing them
  • We would want to use a binomial heap or fibonacci heap