teaching machines

CS 245 Lecture 28 – Heap Demo and Closeout

December 16, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• removing from a heap
• heap demo
• data structure decision tree
• advice

Code

BiggerOrBetter.java

package lecture27;

public class BiggerOrBetter {
  public static void main(String[] args) {
    Person alan = new Person("Alan", 800);
    Person chris = new Person("Chris", 138);
    
    Person better = getBetter(alan, chris, new Comparator<Person>() {
      @Override
      public int compareTo(Person a,
                           Person b) {
//        return a.getName().compareTo(b.getName());
        return new Integer(a.getRep()).compareTo(b.getRep());
      }
    });
    System.out.println(better);
  }
  
  public static Person getBetter(Person a, Person b, Comparator<Person> criteria) {
    if (criteria.compareTo(a, b) > 0) {
      return a;
    } else {
      return b;
    }
  }
}

class Person {
  private String name;
  private int rep;
  
  public Person(String name, int rep) {
    this.name = name;
    this.rep = rep;
  }

  public String getName() {
    return name;
  }

  public int getRep() {
    return rep;
  }
  
  public String toString() {
    return name;
  }
}

interface Comparator<T> {
  public int compareTo(T a, T b);
}

Heap.java

package lecture27;

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Heap<T extends Comparable<T>> {
  private ArrayList<T> items;

  public Heap() {
    items = new ArrayList<T>();
  }

  public int size() {
    return items.size();
  }

  public boolean isEmpty() {
    return items.isEmpty();
  }

  public void clear() {
    items.clear();
  }

  public void add(T newItem) {
    // blindly add newItem to end of list
    // then reheap upward from that point
    items.add(newItem);
    reheapUp(size() - 1);
  }

  public T remove() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    } else if (size() == 1) {
      return items.remove(0);
    } else {
      T max = get(0);
      items.set(0, items.remove(size() - 1));
      reheapDown(0);
      return max;
    }
  }

  public String toString() {
    return items.toString();
  }

  public T get(int i) {
    return items.get(i);
  }

  private void reheapUp(int startingAt) {
    T newItem = get(startingAt);
    int iChild = startingAt;
    int iParent = (iChild - 1) / 2;

    // Reheap up as long as newItem < parent AND hay un padre

    // As long as there's a parent and the newItem is greater than the parent,
    // let's move that parent down the tree. Then, let's move up to the next
    // level.
    while (iChild > 0 && newItem.compareTo(get(iParent)) > 0) {
      items.set(iChild, get(iParent));
      iChild = iParent;
      iParent = (iChild - 1) / 2;
    }

    // Finally, the newItem can be inserted.
    items.set(iChild, newItem);

    // compare newItem to possible parent
    // if newItem > parent
    // put parent in child's spot
    // move up a level
  }

  private void reheapDown(int startingAt) {
    T newItem = get(startingAt);
    int iParent = startingAt;
    int iLeftChild = 2 * iParent + 1;

    // As long as a parent has a child...
    // Find the greater of the two children
    // If the new item is > than the greater child
    // we're done
    // else
    // move greater child up tree
    // make iParent the greater child
    // put newItem in parent's spot

    while (iLeftChild < size()) {
      int iGreaterChild = iLeftChild;
      int iRightChild = iLeftChild + 1;
      if (iRightChild < size() && get(iRightChild).compareTo(get(iLeftChild)) > 0) {
        iGreaterChild = iRightChild;
      }

      // if newItem > greater child
      if (newItem.compareTo(get(iGreaterChild)) > 0) {
        break;
      }

      items.set(iParent, get(iGreaterChild));
      iParent = iGreaterChild;
      iLeftChild = 2 * iParent + 1;
    }

    items.set(iParent, newItem);
  }

  public static void main(String[] args) {
    Heap<Integer> heap = new Heap<Integer>();
    heap.add(6);
    System.out.println(heap);
    heap.add(7);
    System.out.println(heap);
    heap.add(8);
    System.out.println(heap);
    heap.add(1);
    heap.add(100);
    System.out.println("ASdfasd");

    while (!heap.isEmpty()) {
      System.out.println(heap.remove());
    }
  }
}

Circle.java

package lecture27;

import java.awt.Graphics;
import java.awt.Point;

public class Circle implements Comparable<Circle> {
  private Point center;
  private int radius;

  public Circle(Point center,
                int radius) {
    this.center = center;
    this.radius = radius;
  }

  public Point getCenter() {
    return center;
  }

  public int getRadius() {
    return radius;
  }
  
  public void draw(Graphics g) {
    g.fillOval(center.x - radius, center.y - radius, 2 * radius, 2 * radius);
  }

  @Override
  public int compareTo(Circle o) {
    if (radius < o.radius) {
      return -1;
    } else if (radius == o.radius) {
      return 0;
    } else {
      return 1;
    }
  }
}

Circles.java

package lecture27;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Circles extends JPanel implements KeyListener {
  private static final int WIDTH = 1000;
  private static final int HEIGHT = 800;

  private Heap<Circle> circles;

  public Circles() {
    addKeyListener(this);
    setFocusable(true);
    requestFocus();
    circles = new Heap<Circle>();
  }

  @Override
  public void paintComponent(Graphics g) {
    super.paintComponent(g);

    g.setColor(Color.MAGENTA);
    for (int i = 0; i < circles.size(); ++i) {
      circles.get(i).draw(g);
    }

    if (!circles.isEmpty()) {
      g.setColor(Color.RED);
      circles.get(0).draw(g);
    }
  }

  public static void main(String[] args) {
    JFrame frame = new JFrame("Circles");
    frame.add(new Circles());
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(WIDTH, HEIGHT);
    frame.setVisible(true);
  }

  private void generateCircles() {
    Random g = new Random();

    for (int i = 0; i < 650; ++i) {
      circles.add(new Circle(new Point(g.nextInt(WIDTH), g.nextInt(HEIGHT)), g.nextInt(30)));
    }

    repaint();
  }

  private void targetBiggestCircle() {
    if (!circles.isEmpty()) {
      circles.remove();
    }
    repaint();
  }

  @Override
  public void keyPressed(KeyEvent event) {
    if (event.getKeyCode() == KeyEvent.VK_G) {
      generateCircles();
    } else if (event.getKeyCode() == KeyEvent.VK_X) {
      targetBiggestCircle();
    }
  }

  @Override
  public void keyReleased(KeyEvent arg0) {
  }

  @Override
  public void keyTyped(KeyEvent arg0) {
  }
}

Advice

Rob Pike, in Notes on Programming in C:

Fancy algorithms are slow when n is small, and n is usually small.

Donald Knuth, in Structured Programming with Goto Statements:

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.

Haiku