Data Structures Lesson 12

Professor Abdul-Quader

Heaps (Intro)

Synonymous Search Queries

Pseudocode

// checking two queries against each other
boolean queriesMatch = true;
String[] firstWords = query.first.split(" ");
String[] secondWords = query.second.split(" ");
if (firstWords.length != secondWords.length) {
  returns.add(false); // add to list we will be returning
}
for (int i = 0; i < firstWords.length; i++) {
    if (wordsAreNotEqual && wordsAreNotSynonymous) {
      queriesMatch = false;
      break;
    }
}
returns.add(queriesMatch);

synonymous?

// assume we have a List<Pair> synonyms
// wordsAreNotSynonymous
if (!synonyms.contains(new Pair(firstWords[i], secondWords[i]))) {
  // ...
}
  • \(M\) pairs of synonyms, queries have \(N\) words in them.
  • Running time of this snippet?
  • Running time of the whole thing?
  • Obvious improvement?
  • Starter code

Shortest Job First

OS scheduler problem:

  • Keep a priority queue of tasks
  • When the CPU is free, take off the job with highest priority (smallest length)
  • As tasks come in, insert into the priority queue
  • Need to be able to order them?
    • Do we really need to keep them sorted?

Heap Structure

“min”-heap:

  • Complete binary tree
    • all levels completely filled (except possibly the last one)
    • last level: nodes as far left as possible
    • height: \(O(\log(N))\) (why? You proved it already!)
  • Each node is smaller than its children
  • insert and remove

Binary max-heap; courtesey of Wikimedia Commons

Operations

  • min-heap has two operations:
  • insert
  • removeMin
  • Pseudocode? (easiest if we draw it as a tree)

Representation

  • Keep an array
  • Root: position 0
  • Element \(i\):
    • Left child: \(2i + 1\)
    • Right child: \(2i + 2\)
    • No ordering between children

Application

Discuss the following problem at your tables:

Given an unsorted list of \(n\) elements, find the \(k\)-th largest element. (If \(k = 0\), find the largest, if \(k = 1\), find the second largest, etc.) Determine the running time of your algorithm (in terms of \(n\) and \(k\)). (Suppose you are given \(k\) as a parameter to your method: so you don’t need to sort the whole list, just find the \(k\)-th largest one.)

Running time

  • Pseudocode of your solution?
  • Running time?
// reveal.js plugins