Heaps

Question 1

What is a heap?

Answer 1

• A hash table is used when the ordering of elements is not important and we want quick insert, delete and search operations.
• A heap is a tree-like data structure that can be implemented as an array
• Each node of the tree corresponds to an element of the array and every node must satisfy the heap properties

Question 2

Binary Heap

Answer 2

The simplest kind of heap

Question 3

A binary heap can be seen as a binary tree with two additional constraints:

Answer 3

o The shape property the tree is either a full tree or if the last level is not full, the nodes are filled from left to right, i.e. the last level is left-filled
o The heap property each node is greater than or equal (or smaller than or equal) to each of its children

Like AVL trees, an operation on a heap can destroy one of the properties

Question 4

Heap property

Answer 4

§ A binary heap is a complete binary tree implemented as an array

§ Heaps satisfy the heap property: let v and u be nodes of a heap, such that u is a child of v,
o if v.data >= u.data we have a MAX HEAP

o if v.data <= u.data we have a MIN HEAP

Question 5

MIN Heap

Answer 5

Min heap is a complete binary tree where the key of each node is less than the keys of its children

Question 6

MAX Heap

Answer 6

Max heap is a complete binary tree where the key of each node is greater than the keys of its children

Question 7

Heap implementation

Answer 7

Although a heap can be built using a dynamic tree structure, it is most often implemented using an array

This implementation is possible because the heap is, by definition, complete
–>The relationship between a node and its children is fixed and can be calculated

Question 8

How can you store the heap in an array?

Answer 8

Level-order traversal

Question 9

Heap array implementation (parent)

Answer 9

PARENT(i)

return ⎣i/2⎦

Question 10

Heap array implementation (left child)

Answer 10

-The left of a node located at index i is located at 2i

LEFT(i)
return 2i

Question 11

Heap array implementation (right child)

Answer 11

-The right of a node located at index i is located at 2i + 1

RIGHT(i)
return 2i+1

Question 12

A.length vs A.heap.size

Answer 12

A.length = number of elements in the array

A.heap-size = number of elements in the heap stored within A

Question 13

Basic operations

Answer 13

-The basic operations performed on a heap are:
◦ BUILD-MAX-HEAP/ BUILD-MIN-HEAP
—Create a max-heap/min-heap from an unordered array
◦ INSERT A NODE
—New nodes are always inserted at the bottom level (left to right)

◦ DELETE A NODE
—Nodes are removed from the bottom level (right to left)

◦ HEAPSORT
—Sort an array in place

Question 14

For insert and delete we need:

Answer 14

To implement the insert and delete operations, we need two basic operations to maintain/restore the heap property

o HEAPIFY

• –HEAPIFY UP or “percolate up”
• –HEAPIFY DOWN or “percolate down”

o Heapify is the key to maintaining the heap property

Question 15

Building a max heap O(nlogn)

-Uses Heapify-Down O(log n)

Answer 15

§We can build a max-heap in a bottom-up manner by using HEAPIFY-DOWN

◦ Walk backwards through the array from n/2 to 1, calling HEAPIFY-DOWN() on each node
◦ Order of processing guarantees that the children of node i are heaps when i is processed

BUILD-MAX-HEAP(A)
heap-size(A) ← length(A)
for i ← ⎣length(A)/2⎦ downto 1
HEAPIFY-DOWN(A, i)

BUILD-MIN-HEAP(A)
heap-size(A) ← length(A)
for i ← ⎣length(A)/2⎦downto 1 do
HEAPIFY-DOWN**(A, i)

** Modify Heapify-Down to work on a min-heap

Question 16

Other Heap Operations are

Answer 16

• HEAPIFY-DOWN (logn)
• HEAPIFY-UP
• HEAPSORT (nlogn)
• EXTRACT MAX/EXTRACT MIN
• GET MAX/ GET MIN

Question 17

What are heaps useful for?

Answer 17

§ Sorting
◦ Heapsort

§To implement priority queues

Question 18

Heapsort

Answer 18

Goal: Sort an array using heap implementation

§ Idea:
◦ Build a max-heap from the array
◦ Swap the root (the maximum element) with the last element in the array
◦ “Discard” this last node by decreasing the heap size
◦ Call HEAPIFY-DOWN on the new root
◦ Repeat this process until only one node remains

Question 19

Heapsort Pseudocode O(nlogn)

• In place? Yes
• Stable? No

Answer 19

HEAPSORT(A)
  BUILD-MAX-HEAP(A)
  for i ← length(A) downto 2
     swap A[1] ↔ A[i]
     heap-size(A) ← heap-size(A)    – 1
     HEAPIFY-DOWN(A,1)