Heaps

Question 1

Heap

Answer 1

• A tree which satisfies either of the two heap conditions:
  
  • max-heap condition
    
    • root is >= to both children
  • min-heap condition
    
    • root is <= to both children

Question 2

Binary Heap

Answer 2

• A heap that is also a complete binary tree
• Can be represented implicitly with an array b/c it is complete binary tree
• Can use array indexing to find parents and children
• If indexing from 0
  
  • Parent → floor[(i-1) / 2]
  • Child 1 → 2*i + 1
  • Child 2 → 2*i + 2
• In general, people are referring to binary heaps when they discuss heaps

Question 3

Heapify

Answer 3

• Heapify is the process of moving an element with a higher, or lower, priority to its correct location
• 2 variations
  
  • heapfiy-up
  • heapify-down

Question 4

Heapify Up

Answer 4

• Heapify up is the process of moving a node with higher priority up the heap

Steps

1. If node is None, return
2. Compare node with parent node
3. If priority is higher, swap values
4. Perform heapfiy up on parent node
5. Keep going until node is null, or until heap condition is restored

Complexity

Time

Average: O(log n) ♦ Worst: O(log n)

Space

O(1)

Question 5

Heapify Down

Answer 5

• Process of moving an element with lower priority down the heap

Steps

1. If node is null, return
2. Compare node with both children
3. If node’s priority is lower than either child
4. Then swap with the larger of the two children
5. Perform heapify-down on the larger child
6. Keep going until heap condition is restored, or until you don’t have children (leaf)

Complexity

Time

Average: O(log n) ♦ Worst: O(log n)

Space

O(1)

Question 6

Binary Heap

Remove Maximum

Answer 6

• Process of removing max element (element with highest priority) from heap

Steps

1. Store max element (element at index 0)
2. Copy last element into index 0
3. Decrement array
4. Perform heapify down on element at index 0 to move it to its right location

Complexity

Time

Average: O(log n) ♦ Worst: O(log n)

Space

O(1)

Question 7

Binary Heap

Insertion

Answer 7

• Process of inserting an element into binary heap

Steps

1. Add element to end of array
2. Perform heapify up to move element to its correct location

Complexity

Time

Average: O(log n) ♦ Worst: O(log n)

Space

O(1)

Question 8

Binary Heap

Heap Construction

Answer 8

2 appraoched to creating a binary heap

• Naive approach - iterative insertion
  
  • Starting with an empty array, add nodes one by one with insert operations
  • O(n log n)
• BuildHeap
  
  • O(n)

Question 9

BuildHeap

Answer 9

• Algorithm used to transform a normal array into a heap
• Linear time (although it looks O(n log n))

Steps

1. _​_Insert elements into an array
2. We ignore leaves, assuming that they are fine where they are
3. Determine index of last parent node ⇒ floor[(n - 1)/2]
4. Loop from index to front of array, performing heapify-down on each element
5. Keep going until loop ends

Complexity

Time

Average: O(n) ♦ Worst: O(n)

Space

O(1)