CS 245 Lecture 28 – Heap Demo and Closeout
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
One shining moment
I was above all others
But lo, first can’t last
I was above all others
But lo, first can’t last