Priority Queues (Binary Heap)

Priority Queues and Binary Heap

Foreword

This is a complete tutorial for Binary Heaps. We start by defining a more abstract concept called Priority Queue and state the computational problems related to Binary Heaps. In order to grasp the idea of Binary Heap, we assume you are familiar with such topics as basic data structures (arrays, trees) and their properties. In addition, the algorithm analysis requires that you have a basic understanding of Big Oh Notation.

The tutorial is accompanied with exercises comparable to "desk checking" of algorithms. The exercises include pseudocode presentations of the algorithms to be learned and the model solutions show the working of the algorithms by means of algorithm animations in order to better support self studying the material. Your task is to solve the visual algorithm simulation exercises dealing with Insert, DeleteMax, BuildHeap and finally HeapSort algorithms. The exercises are implemented as Java applets and they provide immediate feedback on the correctness of the simulation. The exercise can be solved with many inputs until the algorithm is mastered. See also the model solutions, which include algorithm animations.

1. Introduction

Priority Queue (PQ) is an Abstract Data Type (ADT) that has the following operations 1) insert and 2) find and remove the largest (or smallest) item (DeleteMax or DeleteMin).

Example Use Case: Work Flow Problem

Let a set of jobs J, waiting for completion, be inserted into a priority Queue Q. Each job has a certain priority value p. After the completion of each job, the next job selected is such that has the highest priority. The selected job is removed from Q and started. At any moment, new jobs can be inserted into Q. Thus, there can be arbitrary interleavings of operations in terms of insertions and removals. The challenge is to find such a data structure and algorithms that can most efficiently implement the required operations.

Binary Heap

Binary Heap (aka Heap; other heaps exist as well, but without any extra prefix, heap refers to Binary Heap) is one of the most important implementations for PQ. It is a complete binary tree where all the levels - except possibly the last/lowest level - are full, and in the last/lowest level all the items are on the left. In this case, the data structure can simply be implemented as an array. If the heap is Minimum Heap (MinHeap), the priority of each node is less than the priority of its children. We say that the heap order property for MinHeap is "the father is less (or equal) than its children". Of course, the heap order property can be the other way around in which case we are dealing with Maximum Heap (MaxHeap).

Heap algorithms are based on the following basic idea. First, we make a minor local change. After this, the heap is modified in order to satisfy the heap order property again. The changes are required only in the path from the root to leaf or vice versa.

Heap in a Nutshell

An important implementation for Priority Queue (allows efficient implementations for the operations insert and DeleteMax)
Can be implemented using a simple array due to the fact that a binary heap is
a complete binary tree.

Heap order property (MaxHeap): Father greater than its children

Heap order property (MinHeap): Father less than its children

Next Chapter: Array representation of Binary Heap

This document was last updated 30.5.2011. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.