Usually the word "heap" refers to an unordered pile of things, a mess. Many times it refers to a trash heap, a pile or fill of garbage.
In computer science, a heap usually refers to two different things:
- the memory heap, or area for dynamically allocated memory
- the heap data structure, specifically binary heaps
The use of the word "heap" for these may not be a coincidence! Memory heaps hold dynamically (randomly) allocated memory with no particular order. Heap data structures do not maintain sequential order of their content. In other words, in some way, they are each a respective mess.
Furthering the analogy, some programming languages manage the automatic deallocation of memory within a heap with something called a garbage collector.
The heap data structure is useful for quickly getting the maximum or minimum element from a set. They are generally associated with priority queues, where the element with the highest priority is always at the front of the line.
You may have also heard of heapsort. This is a sorting algorithm that uses a heap to do all the work.
Heap Data Structures
- is a binary tree such that each node dominates key labeling of its children
- is a min-heap when node dominates with smaller keys
- is a max-heap when node dominates with larger keys
Usually when we talk about heaps (data structure) we're referring to binary heaps. There are other types as well.
Introduction to Binary Heaps
I'm bigger and bolder and rougher and tougher. In other words sucker there is no other. I'm the one and only Dominator.
Say you have a list of numbers:
2 7 8 1 5 9 3.
We want to construct a data structure such that we can always get the dominating element in constant time.
In the case of a min-heap it would be
This implies that all the real work needs to happen on element insertion and deletion.
A binary heap uses a complete binary tree.
Recall that complete binary trees:
- have each level filled, with possible exception of last level
- when the last level is incomplete all nodes are filled from the left
Inserting into a binary heap:
- place new element in left most spot (n+1)
- "Bubble Up": if and while (new) element dominates parent
- swap them
Swaps happen between levels, and a tree will have lg(n) levels.
Since there are n items to be inserted, insertion will take
Extracting the dominator from a binary heap:
- remove dominating element from top
- move last added element (bottom-right most leaf) into top
- "Bubble Down": if and while that element does not dominate its children
- swap it with lesser of two children
Implementing Binary Heaps
- can represent binary trees without using pointers (by using an array)
- left child =>
- right child =>
2k + 1
- parent =>
- left child =>
cannot be efficiently searched because it is not a BST
- we don't know any facts that will improve a linear search
- get the dominating element, e.g.
We can store any binary tree in an array without pointers but:
- array still requires empty spots for missing nodes
- methods to save memory make it less flexible