CS 245 Lecture 26 – Heaps and Priority Queues
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
- Suppose you are serializing a tree in a breadth-first fashion—laying out the nodes level by level into an array. Level 0, child 0 goes at index 0. Level 1, child 0 goes at index 1. Level 1, child 1 goes at index 1. Level 2, child 0 at index 2. And so on.
- Given the level number and child number of a node, what is the index where it will be placed in the array?
- What is the index of the same node’s left child?
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
Whom do I serve first?
Friends? Family? Enemies?
I can’t weight to help
Friends? Family? Enemies?
I can’t weight to help