Prerequisites : Heaps vs Priority Queue

WHAT A HEAP and what it IS NOT?

Heap: Is an Abstract Data structure that allows a set of operations that must be supported (such as insert, delete, and extract-min/max).

Disclaimer: A heap can be viewed as both a data structure and an ADT. For now we are viewing it as an ADT—the underlying implementation is not specified.

Array as a heap?

A sorted array can be used to implement the ADT heap (max/min), certain operations will have a higher time complexity, but every insert and delete operation will require us to sort the entire array, resulting in a time complexity of nlogn.

heap= [
				10
				9
				8
				7
				6
				5
				4
				3
				2
				1
			]

Heap as a Binary Tree

To efficiently perform operations such as extracting max/min, insertions, and deletions, we typically use a binary tree as the underlying structure. Since we only need to have the correct location of the max/min, we don’t need to sort the whole set of values. This brings us to the point that a heap is not a sorted structure. It is partially sorted, requiring only that the max or min element is at the top of the heap. Sacrificing the whole sortedness for only the max/min facilitated by a binary tree allows us to perform all heap operations in log(n). (Why log(n) will talk in the sections below).

Heaps Characteristics

Representing heaps as binary trees requires us to satisfy two conditions: