A max-heap is a complete binary tree, where all levels, except the last level, are completely filled. There is no “hole” in the tree. A max-heap should also meet these criteria: the parent’s value is larger than both children’s values in a sub-tree. The largest value of the heap is at the root. The heap is usually related to the priority queue and heapsort.

This post is the max-heap implementation. The min-heap is in the opposite order.

### What data structure is underneath of heap implementation?

A heap is a complete binary tree conceptually. The underlying data structure is an array. Each node’s position in the heap is corresponding to the index in the array. The root’s position is 0, corresponding to the index 0. The node’s position increases by 1 from left to right, from top to bottom.

### What is the formula to get the parent and two children’s positions from the current node’s position in a heap?

parentPos = (pos-1)/2
left = 2*pos+1
right=2*pos+2

### What is the bubble-up algorithm in the heap?

To insert a new element in a heap, the algorithm bubble up is used. It is to put the new item in the first vacant cell of the array. Then move it up in the heap based on its value compared to its parent. In a max-heap, it should be below a node with a larger value and above one or two child nodes with smaller values.

### What is the bubble-down algorithm in the heap?

Bubble-down is an algorithm used in heap deletion. It is to compare the parent node with child nodes in a subtree. In a max-heap, if the parent node’s value is smaller, you should switch the parent element with a child node that has a larger value.

### What is max heap?

A max-heap is a complete binary tree, where all levels, except the last level, are completely filled. There is no “hole” in the tree. A max-heap should also meet these criteria: the parent’s value is larger than both children’s values. The largest value is at the root.

### Map of heap implementations

Part 1 – Max-heap implementation
Part 2 – Min-heap implementation

### Insert

We declare three attributes: heap, length, and maxSize. heap is an array. maxSize is the max length of the array. It is used to initialize the array. length is the actual number of elements in the array. It starts from 0.

To insert a new element, we put the new value at the end of the array. Then we move it up in the heap based on its value compared to its parent. If its value is larger than its parent, it should be switched the position with its parent. We keep doing it until it is below a node with a larger value and above one or two nodes with smaller values. We call this process bubble up.

## Doodle

### Remove

The removal operation is to remove the element at the root, which has the highest value. This is the first element in the underlying array. When we remove the first element in the array, we move the last element to fill out the empty spot. But this element’s value might be smaller than its children’s. To correct this, we compare its value with its children’s values and switch with the child with the larger value. We keep doing it until it is below a node with a larger value and above one or two nodes with smaller values. This process is called bubble down. Bubble down is more complicated than bubble up because it has two children to compare.

## Doodle

Since the underlying data structure is an array, we iterate through all elements to find the one that matches the key.

## Python

### Traversal

The traversal operation is to visit all nodes in the tree. This is the same as a traversal in a binary tree. There are four ways: level order, preorder, inorder, and postorder.

Level order is to visit nodes level by level from top to bottom. The order is the same as the visiting array from index 0 to its length.

## Python

The preorder traversal is to visit the root, traverse the left subtree, and traverse the right subtree. The implementation uses DFS recursion. To get the children’s positions, we use the formula 2*pos+1 for the left child, and 2*pos+2 for the right child.

## Python

The inorder traversal is to traverse the left subtree, visit the root, and traverse the right subtree. The implementation uses DFS recursion. To get the children’s positions, we use the formula 2*pos+1 for the left child, and 2*pos+2 for the right child.

## Python

The postorder traversal is to traverse the left subtree, traverse the right subtree, and visit the root. The implementation uses DFS recursion. To get the children’s positions, we use the formula 2*pos+1 for the left child, and 2*pos+2 for the right child.