teaching machines

CS 245 Lecture 26 – Heaps and Priority Queues

May 1, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• think about this
• priority queues

TODO

• Go visit CERCA today from 2-4 PM on 3rd floor Davies. Talk to some student researchers about their projects. What’s your reaction? Extra credit 1/4 sheet.

Think About This

Code

NumberOfCores.java

package lecture26;

public class NumberOfCores {
  public static void main(String[] args) {
    System.out.println(Runtime.getRuntime().availableProcessors());
  }
}

MaxHeap.java

package lecture26;

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

public class MaxHeap<T extends Comparable<T>> {
  private ArrayList<T> items;
  
  public MaxHeap() {
    items = new ArrayList<>();
  }

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

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

  public void add(T newItem) {
    items.add(newItem);
    reheapUp(items.size() - 1);
  }
  
  private void reheapUp(int iChild) {
    T child = get(iChild);
    int iParent = (iChild - 1) / 2;
    
    if (child.compareTo(get(iParent)) > 0) {
      items.set(iChild, get(iParent));
      items.set(iParent, child);
      reheapUp(iParent);
    }
  }
  
  public T remove() {
    if (isEmpty()) throw new NoSuchElementException();
    
    T max = get(0);
    
    // Take last element, overwrite root.
    items.set(0, items.remove(items.size() - 1));
    
    // Reestablish heap property.
    reheapDown(0);
    
    return max;
  }
  
  private void reheapDown(int iParent) {
    int iLeft = 2 * iParent + 1;
    if (iLeft >= items.size()) {
      return;
    }

    T parent = get(iParent);
    int iBiggerChild = iLeft;
    int iRight = iLeft + 1;
    if (iRight < size() && get(iRight).compareTo(get(iLeft)) > 0) {
      iBiggerChild = iRight;
    }

    if (parent.compareTo(get(iBiggerChild)) < 0) {
      items.set(iParent, get(iBiggerChild));
      items.set(iBiggerChild, parent);
      reheapDown(iBiggerChild);
    }
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    MaxHeap<Integer> heap = new MaxHeap<>();

    System.out.print("Enter #: ");
    while (in.hasNextInt()) {
      heap.add(in.nextInt());
      System.out.print("Enter #: ");
    }
    
    for (int i = 0; i < heap.size(); ++i) {
      System.out.println(heap.get(i));
    }

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

Circle.java

package lecture26;

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 lecture26;

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 MaxHeap<Circle> circles;

  public Circles() {
    addKeyListener(this);
    setFocusable(true);
    requestFocus();
    circles = new MaxHeap<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) {
  }
}

Haiku