Binary Heap

Description

A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to ($\geq$) or less than or equal to ($\leq$) the keys in the node's children, according to some total order.

Structure

Push (sift-up)

To push an element to a heap, we can perform this algorithm:

1. Push the element to the bottom level of the heap at the leftmost open space.
2. Compare the pushed element with its parent; if they are in the correct order, stop.
3. If not, swap the element with its parent and return to the previous step.

Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with its parent, are called the sift-up operation.

Pop (sift-down)

The procedure for popping the root from the heap while retaining the heap property is as follows:

1. Replace the root of the heap with the last element on the last level.
2. Remove the last element on the last level.
3. Compare the new root with its children; if they are in the correct order, stop.
4. If not, swap the element with one of its children and return to the previous step.

Steps 3 and 4, which restore the heap property by comparing and possibly swapping a node with one of its children, are called the sift-down operation.

Delete

Deleting an arbitrary element can be done as follows:

1. Swap the element we want to delete with the last element.
2. Sift-down or sift-up to restore the heap property.

Change

1. Change value by the given index.
2. If parent heap property is violated do sift-up.
3. Else if changed node heap property is violated do sift-down.

Example

Let's look at several examples of working with a max binary heap. We start with empty heap.

Code

                        class BinaryHeap:
                            def __init__(self, container: Any = list, compare: Any = operator.ge) -> None:
                                self.container = container()
                                self.compare = compare
                        
                            def sift_up(self, key: int):
                                if len(self.container) > key:
                                    while (
                                        key > 0
                                        and self.compare(self.container[(key - 1) >> 1], self.container[key])
                                        == False
                                    ):
                                        (self.container[(key - 1) >> 1], self.container[key]) = (
                                            self.container[key],
                                            self.container[(key - 1) >> 1],
                                        )
                                        key >>= 1
                        
                            def sift_down(self, key: int):
                                if len(self.container) > key:
                                    while (
                                        2 * key + 1 < len(self.container)
                                        and self.compare(self.container[key], self.container[2 * key + 1])
                                        == False
                                    ) or (
                                        2 * key + 2 < len(self.container)
                                        and self.compare(self.container[key], self.container[2 * key + 2])
                                        == False
                                    ):
                                        if 2 * key + 2 < len(self.container):
                                            if (
                                                self.compare(
                                                    self.container[2 * key + 1], self.container[2 * key + 2]
                                                )
                                                == True
                                            ):
                                                (self.container[2 * key + 1], self.container[key]) = (
                                                    self.container[key],
                                                    self.container[2 * key + 1],
                                                )
                                                key = 2 * key + 1
                                            else:
                                                (self.container[2 * key + 2], self.container[key]) = (
                                                    self.container[key],
                                                    self.container[2 * key + 2],
                                                )
                                                key = 2 * key + 2
                                        else:
                                            (self.container[2 * key + 1], self.container[key]) = (
                                                self.container[key],
                                                self.container[2 * key + 1],
                                            )
                                            key = 2 * key + 1
                        
                            def push(self, new_value: Any):
                                self.container.append(new_value)
                                self.sift_up(len(self.container) - 1)
                        
                            def remove(self, key: int):
                                if len(self.container) > key:
                                    (self.container[len(self.container) - 1], self.container[key]) = (
                                        self.container[key],
                                        self.container[len(self.container) - 1],
                                    )
                                    self.container.pop()
                                    self.sift_down(key)
                        
                            def pop(self):
                                self.remove(0)
                        
                            def change(self, key: int, new_value: Any):
                                if len(self.container) > key and self.container[key] != new_value:
                                    self.container[key] = new_value
                                    if (
                                        key > 0
                                        and self.compare(self.container[(key - 1) >> 1], self.container[key])
                                        == False
                                    ):
                                        self.sift_up(key)
                                    else:
                                        self.sift_down(key)
                        
                            def top(self) -> Any:
                                return self.container[0] if len(self.container) > 0 else None
                        
                            def size(self) -> int:
                                return len(self.container)