Binary Heaps

A binary heap is a data structure based on a complete binary tree that allows for the rapid extraction of the first item in an ordered set. Heaps are used in various common algorithms, including heapsort, which is used to order elements in a collection.

Complete Tree Constraint

When building a binary tree, we begin with a root node that can have zero, one, or two offspring. Each child node can also have zero, one, or two children. These nodes can also have up to two children, and this process can be repeated indefinitely.

(Source: Link)

In the above image, the root node has two offspring. The child on the left has two children, whereas the child on the right only has one. Because they have no progeny, the three nodes at the lowest level are referred to as leaf nodes.

A binary tree is said to be a perfect tree if all of its leaf nodes are at the same level and all of its non-leaf nodes have two children. This is not a prerequisite for a heap.

The above image shows the perfect binary tree.

A heap’s constraint is that the tree must be complete. This signifies that, with the exception of the lowest level, every level of the tree is totally filled. The tree’s last level does not have to be filled. The nodes on the lowest level, on the other hand, must be as far to the left of the tree as possible.

Ordering Constraint

Although the image above is a complete binary tree, it does not meet the ordering criteria and hence does not qualify as a heap. Heaps are used for sorting operations, and the root node is always the first item to be sorted when the heap’s contents are sorted. Every child node must be organized in relation to its parent.

Because the parent-to-child ordering is correct and the binary tree is complete, the figure above depicts a valid heap. This graphic depicts a minimum heap. This is a heap that is structured in such a way that the smallest value appears at the top. A max heap is an inverse, in which the maximum value is maintained in the root node and each child has the same or lesser value than its parent.

Conclusion

In this article, I described what is a Binary Heap, Complete Tree Constraint, and Ordering tree Constraint. To know more about it, Tutort Academy offers Data Structure Tutor assistance and programs for the working professionals.