Insertion

Insert 3: slide 10 down, slide 5 down, then put 3 into that place.

Insertion

Pseudocode

void insert(number) {
  int index = tail;
  int parent = (tail - 1) / 2
  while (index > 0 && array[parent] > array[index]) {
    slide array[parent] down
    update index / parent
  }
  array[index] = number
  tail++
}

Exercise

• Implement the insertion algorithm on replit.
• Test it out with the main method (which inserts several random numbers and then outputs the array).
• Should be able to see that the array is a valid heap.

Video

Image

Image

Exercise

• Implement this on replit.
• Test it out by uncommenting the last part on replit.
• You should see that the elements that were inserted are now printed in sorted order!

Video

Idea 1

• Put everything into a max-heap.
• Take off the first \(k\) elements.

Running Time

• Insert \(n\) elements into a heap: \(O(n \log(n))\)?
  • Later today: improve it to \(O(n)\)!
• Take off \(k\) elements: \(O(k \log(n))\).
• Total: \(O(n + k \log(n))\). If \(k\) is small, then \(O(n)\). Large: \(O(n \log(n))\).
• Other ideas?
  • Do you need to store the whole array?
  • Hint: find the second largest in \(O(n)\) time: keep track of the largest and second largest as you go through the array. Just update those two.

Idea 2

• Keep track of the \(k\) largest elements.
• …but use a min-heap!
• In a loop:
  • if \(i < k\), add to the heap
  • Otherwise, check if list[i] > minimum. If so, remove min and add \(list[i]\).
• At the end: minimum is the \(k\)-th largest!

Running Time

• Add \(k\) elements to the heap: \(O(k \log(k))\)
• Possibly remove / insert \(n - k\) times: \(O(n \log(k))\).
• Get the minimum element: \(O(1)\).
• Total: \(O(n \log(k))\).

Improvement

• That used \(O(n)\) extra space.
• If we have an array of length \(n\), can’t we just use it?
  • Turn it into a (max-)heap!
  • How?
• Then, for each \(i = 0, \ldots, n - 1\):
  • swap max with \(i\)-the element from end of array.
  • rebuild the “heap” with 1 less element.
  • ie: pretend that the heap goes from \(0\) to \(n - i\)

buildHeap

How do we turn an array into a heap?

• For each element: check if it’s smaller than its “children”.
• If so, slide it down into place.
• Start at the beginning or the end?
• Running time?
• Try to write this yourself: will be on homework 3.

Video