Heap Data Structure

Heap is a binary tree. The binary tree doesn’t look like the traditional Homo sapiens family: children have only 1 parent, and this 1 parent may have only two children maximum. There are 2 types of heaps:

• Max-heap: when each parent's value is more significant than its children's value;
• Min-heap: when each parent's value is lower than its children’s value.

Let’s learn some basic heap operations:

• Heapify;
• Insert;
• Deletion.

Heapify

Heapify is a process of creating a heap data structure from a binary tree.

Once the tree is composed, it is needed to create precisely the heap(max-/min-heap).

To do that, we need to replace nodes due to the rules of the max-/min-heap.

In the next chapter, we will practice heaping.

Insertion It is straightforward to insert an element into the heap. We need to:

• Insert it as a leave (the end branches);
• Perform heapifying.

Deletion

To delete the node from the heap, you need to:

• Swap the element you want to delete with the last element;
• Delete the last element;
• Perform heapifying.