A heap is a (nearly) complete binary tree laid out as an array. An important property of the heap says that every node has a value less than or equal to it's children for a min heap. For a max heap, every node has a value greater than or equal to it's children.
Let's take the array $A = [a, b, c, d, e, f, g]$ and write it as a tree:
```mermaid
flowchart TB
a --> b & c
b --> d & e
c --> f & g
```
The first element $a$ is the root.
For a parent node $A[i]$
- $A[2i]$ is the left child if $2i \le n$
- $A[2i + 1]$ is the right child if $2i + 1 \le n$.
The parent of any child is at the floor of $j/2$.
The **depth** (sometimes **height**) of the heap is the number of layers in the tree.
Each subtree in a heap is also a heap.
Consider that a heap does not need to be a sorted array to have the min heap (or max heap) property. A sorted array is a heap, but not necessarily vice versa.
### bubble up
Bubble up is a heap [[primitive]] that fixes a broken heap by "bubbling up" a child element that is in the wrong position.
Bubble up is implemented as a [[base/Algorithms/recursion|recursive]] function. The pseudocode is:
```python
bubble_up(A, j):
if j <= 1:
return
elif A[j] < A[j//2]:
swap(A[j], A[j//2])
bubble_up(A, j//2)
return
```
Bubble up runs in $\Theta (\log_2 n)$.
### bubble down
Bubble down is a heap [[primitive]] that fixes a broken heap by "bubbling down" a parent element that is in the wrong position.
Bubble down is implemented as a [[base/Algorithms/recursion|recursive]] function. The pseudocode is:
```python
bubble_down(A, j):
left = 2*i
right = 2*i + 1
if left > n:
return
if left <= n and right > n: # A has 1 child
if A[i] > A[left]:
swap(A[i], A[left])
bubble_down(A, left)
else:
# Find smaller of two children
if A[left] < A[right]:
smaller = left
else:
smaller = right
# Swap
swap(A[i], A[smaller])
# Bubble down
bubble_down(A, smaller)
```
Bubble down, like bubble up, runs in $\Theta (\log_2 n)$.
### insert
To insert an element in a heap, simply append it and then use bubble up to position it.
### delete
To delete an element in a heap, delete the element and replace it with the very last element of the array, adjusting the size to $n-1$. Then either bubble up the element that was moved if it is less than its parent or bubble down if it is greater than its children.
### heapify
Heapify will convert any array into a heap. The idea is to start at the end of the first half of the array and bubble down each element as needed until a heap is achieved. The last half of the array are the terminal leaves and don't require bubbling.
```python
# For min heap
for i = n/2 down to 1:
bubbleDown(A, i)
```
The [[complexity]] of heapify is linear $\Theta(n)$.
Python's inbuilt `heapq` provides access to priority queues.
> [!Tip]- Additional Resources
> [Heapq](https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/)