Heap

Introduction

A heap is a data-structure that implements a priority queue, by using a complete-binary- tree. Each node of the tree contains one element, and they are organized by their key values, such that

Therefore, the root has the smallest key value. Below is an example heap with 6 nodes. The values inside the nodes are the key values.

Finally, a heap of $n$ nodes is represented efficiently by an array $A[1: n]$, where $A[i]$ represents node $i$. For example, the array representation of the above heap is as shown below.