Advertisement
Guest User

Untitled

a guest
Dec 2nd, 2015
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.98 KB | None | 0 0
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Vector;
  4.  
  5. /**
  6. * Course: EECS 114 Fall 2015
  7. *
  8. * First Name: Franklin Last Name: Hool Lab Section: 1A email address:
  9. * fhool@uci.edu
  10. *
  11. *
  12. * Assignment: Assignment 4 Filename : PriorityQueue
  13. *
  14. * I hereby certify that the contents of this file represent my own original
  15. * individual work. Nowhere herein is there code from any outside resources such
  16. * as another individual, a website, or publishings unless specifically
  17. * designated as permissible by the instructor or TA.
  18. */
  19. public class PriorityQueue {
  20. MinHeap heap;
  21. Vector<Node> list;
  22.  
  23. public class Node {
  24. private int key;
  25. private int value;
  26.  
  27. Node(int key, int value) {
  28. this.key = key;
  29. }
  30.  
  31. }
  32.  
  33. public class HeapNode {
  34. private int key;
  35. private Queue<Integer> values;
  36.  
  37. HeapNode(int key, int value) {
  38. values = new LinkedList<Integer>();
  39. values.add(value);
  40. }
  41.  
  42. public void addNode(int value) {
  43. values.add(value);
  44. }
  45.  
  46. public int removeNode() {
  47. return values.remove();
  48. }
  49. }
  50.  
  51. PriorityQueue() {
  52.  
  53. }
  54.  
  55. public void buildPriorityQueue(int[] array) {
  56. Vector<Node> nodes = new Vector<Node>();
  57. for (int i = 0; i < array.length / 2; i++) {
  58. Node node = new Node(array[i], array[i + 1]);
  59. nodes.addElement(node);
  60. i++;
  61. }
  62. heap = new MinHeap(nodes);
  63. }
  64.  
  65. public class MinHeap {
  66. int heapSize = 0;
  67. Vector<HeapNode> list;
  68. int i;
  69. public static final int CAPACITY = 100;
  70.  
  71. MinHeap() {
  72. }
  73.  
  74. MinHeap(Vector<Node> A) {
  75. for (int i = 0; i < A.size(); i++) {
  76. if (!list.contains(A.get(i).key)) {
  77. list.add(new HeapNode(A.get(i).key, A.get(i).value));
  78. } else {
  79. list.get(i).addNode(A.get(i).value);
  80. }
  81.  
  82. }
  83. buildMinHeap();
  84.  
  85. }
  86.  
  87. public void buildMinHeap() {
  88. /* Trickle down parents */
  89. for (i = heapSize / 2 - 1; i >= 0; i--) {
  90. trickleDown(i);
  91. }
  92. }
  93.  
  94. int heapMin() {
  95. /* Throw exception if h is empty */
  96. if (currentSize() == 0) {
  97. throw new IndexOutOfBoundsException();
  98. }
  99.  
  100. int temp = list.get(0).key;
  101.  
  102. /* Search for smallest value */
  103. for (i = 0; i < currentSize(); i++) {
  104. if (temp > list.get(i).key) {
  105. temp = list.get(i).key;
  106. }
  107. }
  108. /* Return smallest value */
  109. return temp;
  110. }
  111.  
  112. void heapExtractMin() {
  113. /* Throw exception if h is empty */
  114. if (currentSize() == 0) {
  115. throw new IndexOutOfBoundsException();
  116. }
  117. /* Extract the min */
  118. for (i = 0; i < currentSize(); i++) {
  119. if (i + 1 == CAPACITY) {
  120. break;
  121. }
  122. list.get(i).key = list.get(i + 1).key;
  123. }
  124. heapSize--;
  125.  
  126. /* Trickle up */
  127. for (i = 0; i < currentSize(); i++) {
  128. trickleUp(i);
  129. }
  130. }
  131.  
  132. void minHeapInsert(int key) {
  133. /* Throw exception is h is full */
  134. if (currentSize() == CAPACITY) {
  135. throw new IndexOutOfBoundsException();
  136. }
  137. /* Assign insert key to end of list */
  138. list.get(list.size()).key = key;
  139. heapSize++;
  140. /* Trickle up */
  141. for (i = 0; i < currentSize(); i++) {
  142. trickleUp(i);
  143. }
  144. }
  145.  
  146. private void trickleDown(int index) {
  147. int temp;
  148.  
  149. /* Checks if parent has right child */
  150. if (index * 2 + 2 <= list.size()) {
  151. if (list.get(index * 2 + 2).key == 0) {
  152. if (list.get(index).key > list.get(index * 2 + 1).key) {
  153. temp = list.get(index).key;
  154. list.get(index).key = list.get(index * 2 + 1).key;
  155. list.get(index * 2 + 1).key = temp;
  156. trickleDown(2 * index + 1);
  157. }
  158. } else {
  159. /* Comparison between parent and left and right child */
  160. if (list.get(index).key > list.get(index * 2 + 1).key
  161. || list.get(index).key > list.get(index * 2 + 2).key) {
  162. if (list.get(index * 2 + 1).key < list.get(index * 2 + 2).key) {
  163. temp = list.get(index).key;
  164. list.get(index).key = list.get(index * 2 + 1).key;
  165. list.get(index * 2 + 1).key = temp;
  166. trickleDown(2 * index + 1);
  167. }
  168. /* Comparison between parent and right child */
  169. else if (list.get(index * 2 + 1).key > list.get(index * 2 + 2).key) {
  170. temp = list.get(index).key;
  171. list.get(index).key = list.get(index * 2 + 2).key;
  172. list.get(index * 2 + 2).key = temp;
  173. trickleDown(2 * index + 2);
  174. }
  175. }
  176. }
  177.  
  178. }
  179. }
  180.  
  181. private void trickleUp(int index) {
  182. /* Assign parent index */
  183. int parent = (index - 1) / 2;
  184. int temp;
  185.  
  186. /* Parent comparison with index */
  187. if (list.get(parent).key > list.get(index).key) {
  188. temp = list.get(parent).key;
  189. list.get(parent).key = list.get(index).key;
  190. list.get(index).key = temp;
  191. trickleUp(parent);
  192. }
  193. }
  194.  
  195. int currentSize() {
  196. /* Return current size of the heap */
  197. return heapSize;
  198. }
  199.  
  200. public void printHeap() {
  201. int i = 0;
  202. int k = 1;
  203. while (i < currentSize()) {
  204. for (int j = 0; j < k; j++) {
  205. if (i < currentSize()) {
  206. System.out.print(list.get(i).key + " ");
  207. i++;
  208. }
  209. }
  210. k = k * 2;
  211. System.out.println("");
  212. }
  213. }
  214. }
  215.  
  216. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement