Data Structures & Algorithms Lecture Notes

Outline

The array-based implementation of trees is not easily dynamic.
It is, however, the bases for a number of useful data structures and algorithms.
- It's also a cheap way to implement binary trees in some cases.
- In particular, when the number of elements is bounded.

binary tree indexing

If a binary-tree node is stored at index i, its
- left child is stored at index 2i + 1 and
- its right child is stored at index 2(i + 1) and
The root of the binary tree is stored at index 0.

A heap is a binary tree T satisfying
1. the value stored at any node n in T is not less (or greater) than the values stored at n's children.
  - This is the heap property.
2. T is balanced.

A heap's root value is the largest (or smallest) value in the heap.
Heaps and binary search trees are incomparable.
The heap property can be maintained with O(log n) work per element.
Maintaining the heap property is easier than is maintaining the binary search tree property.
- A single pass up or down the heap is enough.

The heap ADT is stack-like at the interface.
- But no LIFO ordering.
create(), destroy(), … maintenance operations.
add(data) and data remove() manipulation operations.
- Remove only the root.
size(), empty(), data top(), … query operations.

Create a heap containing the contents of an array.
```
heap::create(T a[], unsigned n)
```
- This operation is often called heapify.
Create a heap by merging two other heaps.
```
heap::create(heap h₁, heap h₂)
```
Merge one heap into another.
```
heap::merge(heap h)
```

a simple implementation for a heap

Add a new element to a heap in two steps:


i = count++
d[i] = e
while i ≠ 0
  p = (i - 1)/2
  if d[p] ≥ d[i], break
  swap(d[p], d[i])
  i = p

example priority queue enqueue

Heap remove is restricted to the root.
Heap remove is a simpler and harder than binary-search tree remove.
- Simpler because any leaf may do.
- Harder because the heap property has to be maintained.
Replace the root with a leaf.
Bubble down the root value to maintain the heap property.

example heap remove

A regular queue stores elements in FIFO order.
Assign each queue element a priority that can be ordered.
A priority queue stores elements in increasing (min queue) or decreasing (max queue) order.
- No more FIFO ordering.
- Sometimes no more end-restricted access either (canceling queued entries).

An array-based heap provides an efficient implementation of a priority queue.
New entries are enqueued at the last element and bubbled up to maintain the heap property.
The head is dequeued by replacing it with the last element and bubbling it down to its proper location.
Heaps provide O(log n) behavior.
- Vs. O(n) for a non-heap implementation.

Remember this?
A heap can answer these questions at a cost of O(log n) per question.
- That's worst-case O(n log n) total.

Given an array of elements, heapify it.
- Bubble up successive elements from left to right.
- This costs O(n log n).
Remove the max heap element and store it in the open space.

heapsort(a[], n)

  for i = 1 to n - 1
    bubble-up(a, i)

  for i = n - 1 to 1
    swap(a[0], a[i])
    bubble-down(i)

heapsort vs quicksort on ints

heapsort vs quicksort on points

The heap property means parents are at least (or most) their children.
- The heap property is different from the binary-search property.
A heap is a binary tree obeying the heap property.
Array-implemented heaps are common.
- Simple, fast, small.
Heaps are the basis for priority queues.

This page last modified on 3 December 2008.