Max heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled and all the nodes in the last level are as left as possible. Max heap should also meets this criteria: the parent’s key is larger than both children’s keys. The largest value is at the root. Heap is related to priority queue and heapsort.

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

Table of Content

max heap

What is the data structure underneath of heap implementation?

max heap

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 upper level to lower level.

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

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

What is bubble up in heap insertion?

To insert a new element in a heap, the algorithm bubble up (trickle up or heap 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 key and above 1 or 2 (child) nodes with smaller keys.

What is bubble down in heap deletion?

Removal in heap is to remove the element at the root of the heap. This element is also the first in the underlying array. To fill the “hole”, move the last element to fill in. Then use the algorithm bubble down (trickle down or heap down) to move this element down in the heap. It should be below a “larger” node and above 1 or 2 “smaller” nodes in a max-heap.


Map of heap implementations

you are here

Part 1 – Max-heap implementation
Part 2 – Min-heap implementation
Part 3 – Priority queue implementation with heap – iterative solution
Part 4 – Priority queue implementation with heap – recursive solution
Part 5 – Heapsort – iterative and recursive solutions


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 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 based on its value compared to its parent. If it’s value larger than its parent, it should be switched the position with its parent, until it is below a larger node and above a smaller one. We call this process bubble up or heap up.

Java

Javascript

Python

Doodle

priority queue heap iterative


Remove

The remove operation is to remove the element with the highest value, which is the first one in the 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, until it is below a larger node and above a smaller one. This process is called bubble down or heap down. Heap down is more complicated than heap up because it has two children to compare.

Java

Javascript

Python

Doodle

priority queue heap delete

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

Java

Javascript

Python


Traversal

Traversal is to visit all nodes in the tree in some specified order. Please note the heap is a tree in conceptual context, the underlying implementation is array. Therefore there are no actual nodes as we see in the binary tree implementation (there is no root node). But we still can traverse all elements in the same way as any tree traversal – by level order, preorder, inorder and postorder.

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

Java

Javascript

Python

Preorder is to visit the root, traverse the left subtree, traverse the right subtree. The implementation is using dfs recursion. To get the children “node”, we use the formula 2*pos+1 for left child, and 2*pos+2 for right child.

Java

JavaScript

Python

Inorder is to traverse the left subtree, visit the root, traverse the right subtree. The implementation is using dfs recursion. To get the children “node”, we use the formula 2*pos+1 for left child, and 2*pos+2 for right child.

Java

Javascript

Python

Postorder is to traverse the left subtree, traverse the right subtree, visit the root. The implementation is using dfs recursion. To get the children “node”, we use the formula 2*pos+1 for left child, and 2*pos+2 for right child.

Java

JavaScript

Python


Free download

Download max-heap implementation in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python