Heaps

Introduction

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

heap-labeled tree:

• 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.

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 1. This implies that all the real work needs to happen on element insertion and deletion.