Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Vector;
- /**
- * Course: EECS 114 Fall 2015
- *
- * First Name: Franklin Last Name: Hool Lab Section: 1A email address:
- * fhool@uci.edu
- *
- *
- * Assignment: Assignment 4 Filename : PriorityQueue
- *
- * I hereby certify that the contents of this file represent my own original
- * individual work. Nowhere herein is there code from any outside resources such
- * as another individual, a website, or publishings unless specifically
- * designated as permissible by the instructor or TA.
- */
- public class PriorityQueue {
- MinHeap heap;
- Vector<Node> list;
- public class Node {
- private int key;
- private int value;
- Node(int key, int value) {
- this.key = key;
- }
- }
- public class HeapNode {
- private int key;
- private Queue<Integer> values;
- HeapNode(int key, int value) {
- values = new LinkedList<Integer>();
- values.add(value);
- }
- public void addNode(int value) {
- values.add(value);
- }
- public int removeNode() {
- return values.remove();
- }
- }
- PriorityQueue() {
- }
- public void buildPriorityQueue(int[] array) {
- Vector<Node> nodes = new Vector<Node>();
- for (int i = 0; i < array.length / 2; i++) {
- Node node = new Node(array[i], array[i + 1]);
- nodes.addElement(node);
- i++;
- }
- heap = new MinHeap(nodes);
- }
- public class MinHeap {
- int heapSize = 0;
- Vector<HeapNode> list;
- int i;
- public static final int CAPACITY = 100;
- MinHeap() {
- }
- MinHeap(Vector<Node> A) {
- for (int i = 0; i < A.size(); i++) {
- if (!list.contains(A.get(i).key)) {
- list.add(new HeapNode(A.get(i).key, A.get(i).value));
- } else {
- list.get(i).addNode(A.get(i).value);
- }
- }
- buildMinHeap();
- }
- public void buildMinHeap() {
- /* Trickle down parents */
- for (i = heapSize / 2 - 1; i >= 0; i--) {
- trickleDown(i);
- }
- }
- int heapMin() {
- /* Throw exception if h is empty */
- if (currentSize() == 0) {
- throw new IndexOutOfBoundsException();
- }
- int temp = list.get(0).key;
- /* Search for smallest value */
- for (i = 0; i < currentSize(); i++) {
- if (temp > list.get(i).key) {
- temp = list.get(i).key;
- }
- }
- /* Return smallest value */
- return temp;
- }
- void heapExtractMin() {
- /* Throw exception if h is empty */
- if (currentSize() == 0) {
- throw new IndexOutOfBoundsException();
- }
- /* Extract the min */
- for (i = 0; i < currentSize(); i++) {
- if (i + 1 == CAPACITY) {
- break;
- }
- list.get(i).key = list.get(i + 1).key;
- }
- heapSize--;
- /* Trickle up */
- for (i = 0; i < currentSize(); i++) {
- trickleUp(i);
- }
- }
- void minHeapInsert(int key) {
- /* Throw exception is h is full */
- if (currentSize() == CAPACITY) {
- throw new IndexOutOfBoundsException();
- }
- /* Assign insert key to end of list */
- list.get(list.size()).key = key;
- heapSize++;
- /* Trickle up */
- for (i = 0; i < currentSize(); i++) {
- trickleUp(i);
- }
- }
- private void trickleDown(int index) {
- int temp;
- /* Checks if parent has right child */
- if (index * 2 + 2 <= list.size()) {
- if (list.get(index * 2 + 2).key == 0) {
- if (list.get(index).key > list.get(index * 2 + 1).key) {
- temp = list.get(index).key;
- list.get(index).key = list.get(index * 2 + 1).key;
- list.get(index * 2 + 1).key = temp;
- trickleDown(2 * index + 1);
- }
- } else {
- /* Comparison between parent and left and right child */
- if (list.get(index).key > list.get(index * 2 + 1).key
- || list.get(index).key > list.get(index * 2 + 2).key) {
- if (list.get(index * 2 + 1).key < list.get(index * 2 + 2).key) {
- temp = list.get(index).key;
- list.get(index).key = list.get(index * 2 + 1).key;
- list.get(index * 2 + 1).key = temp;
- trickleDown(2 * index + 1);
- }
- /* Comparison between parent and right child */
- else if (list.get(index * 2 + 1).key > list.get(index * 2 + 2).key) {
- temp = list.get(index).key;
- list.get(index).key = list.get(index * 2 + 2).key;
- list.get(index * 2 + 2).key = temp;
- trickleDown(2 * index + 2);
- }
- }
- }
- }
- }
- private void trickleUp(int index) {
- /* Assign parent index */
- int parent = (index - 1) / 2;
- int temp;
- /* Parent comparison with index */
- if (list.get(parent).key > list.get(index).key) {
- temp = list.get(parent).key;
- list.get(parent).key = list.get(index).key;
- list.get(index).key = temp;
- trickleUp(parent);
- }
- }
- int currentSize() {
- /* Return current size of the heap */
- return heapSize;
- }
- public void printHeap() {
- int i = 0;
- int k = 1;
- while (i < currentSize()) {
- for (int j = 0; j < k; j++) {
- if (i < currentSize()) {
- System.out.print(list.get(i).key + " ");
- i++;
- }
- }
- k = k * 2;
- System.out.println("");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement