5. YSC2229 Lecture Notes, Week 05

• 5.1. Printing and Validating Generic Arrays
• 5.2. Binary Heaps
  • 5.2.1. Motivation: finding a maximum in a changing array
  • 5.2.2. Definition of a binary heap
  • 5.2.3. Checking that an array is a heap
• 5.3. Maintaining Binary Heaps
  • 5.3.1. “Heapifying” elements of an array
  • 5.3.2. Complexity of heapify
  • 5.3.3. Building a heap from an array
• 5.4. Heapsort
  • 5.4.1. Heapsort Complexity
  • 5.4.2. Evaluating Heapsort
  • 5.4.3. Which sorting algorithm to choose?
• 5.5. Priority Queues
  • 5.5.1. Creating Priority Queues
  • 5.5.2. Operations on Priority Queues
  • 5.5.3. Working with Priority Queues
• 5.6. Exercises
  • 5.6.1. Mandatory exercises
  • 5.6.2. Recommended exercises
  • 5.6.3. Exercise 1
  • 5.6.4. Exercise 2
  • 5.6.5. Exercise 3
  • 5.6.6. Exercise 4
  • 5.6.7. Exercise 5
  • 5.6.8. Exercise 6
  • 5.6.9. Exercise 7

Supplementary materials

• Code from Week 5: binary heaps and priority queues.