teaching machines

CS 245 Lecture 26 – Heaps and Priority Queues

Agenda

• what ?s
• 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.

• 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);
}

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()) {
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;

public Circle(Point center,
this.center = center;
}

public Point getCenter() {
return center;
}

}

public void draw(Graphics g) {
}

@Override
public int compareTo(Circle o) {
return -1;
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() {
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.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) {
}

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