Heap and Tries
What is HEAP? A heap is a tree-based data structure in which all the nodes of the tree are in a specific order. For example, if X is the parent node of Y , then the value of X follows a specific order with respect to the value of Y and the same order will be followed across the tree. The maximum number of children of a node in a heap depends on the type of heap. However, in the more commonly-used heap type, there are at most 2 children of a node and it's known as a binary heap. In a binary heap, if the heap is a complete binary tree with N nodes, then it has the smallest possible height which is l o g 2 N . Illustration of Heap In the diagram above, you can observe a particular sequence, i.e each node has greater value than any of its children. Suppose there are N Jobs in a queue to be done, and each job has its own priority. The job with maximum priority will get completed first than others. At each instant, we are completing a job with maxi