5. Week 05: Binary Heaps and Priority Queues

• 5.1. Printing and Validating Generic Arrays
• 5.2. Best-Worst Case for Comparison-Based Sorting
• 5.3. Sorting in Linear Time
  • 5.3.1. Simple Bucket Sort
  • 5.3.2. Enhanced Bucket Sort
  • 5.3.3. Stability of sorting
  • 5.3.4. Radix Sort
• 5.4. Binary Heaps
  • 5.4.1. Finding a maximum in a changing array
  • 5.4.2. Definition of a binary heap
  • 5.4.3. Checking that an array is a heap
• 5.5. Maintaining Binary Heaps
  • 5.5.1. “Heapifying” elements of an array
  • 5.5.2. Complexity of heapify
  • 5.5.3. Building a heap from an array
• 5.6. Heapsort
  • 5.6.1. Heapsort Complexity
  • 5.6.2. Evaluating Heapsort
  • 5.6.3. Which sorting algorithm to choose?
• 5.7. Priority Queues
  • 5.7.1. Creating Priority Queues
  • 5.7.2. Operations on Priority Queues
  • 5.7.3. Working with Priority Queues
• 5.8. Exercises
  • 5.8.1. Exercise 1
  • 5.8.2. Exercise 2
  • 5.8.3. Exercise 3
  • 5.8.4. Exercise 4
  • 5.8.5. Exercise 5
  • 5.8.6. Exercise 6