Heap

Motivation

• Search
• Sorts in place
• Top N items

Definition

A binary heap is a heap data structure created using an array (or more precisely a vector).

More formally it is a binary tree with:

* Shape property -

The tree is mostly complete with only the deepest level left unfilled. This level is filled from left until right.

• Heap property - Each node is greater than or equal to its decendant nodes (max) or Each node is less than or equal to its descendant nodes (min)

Attributes

• length, size
• left
• right
• parent

Operations

• heapify
• insert (push)
• extract (pop)