daily pastebin goal
58%
SHARE
TWEET

Untitled

a guest May 16th, 2018 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class PriorityQueue {
  2.     private static class MaxHeap {
  3.         private int size;
  4.         private Long[] array;
  5.        
  6.         public MaxHeap(int size) {
  7.             this.size = 0;
  8.             this.array = new Long[size];
  9.         }
  10.        
  11.         private static int parent(int index) {
  12.             return (index - 1) >> 1;
  13.         }
  14.        
  15.         private static int right(int index) {
  16.             return (index << 1) + 2;
  17.         }
  18.        
  19.         private static int left(int index) {
  20.             return (index << 1) + 1;
  21.         }
  22.        
  23.         public void insert(Long l) {
  24.             if(size < array.length) {
  25.                 array[size] = l;
  26.                 int ptr = size++;
  27.                
  28.                 // Swim up the MaxHeap
  29.                 Long temp;
  30.                 while(ptr > 0) {
  31.                     if(array[ptr] > array[parent(ptr)]) {
  32.                         temp = array[ptr];
  33.                         array[ptr] = array[parent(ptr)];
  34.                         array[parent(ptr)] = temp;
  35.                         ptr = parent(ptr);
  36.                     } else break;
  37.                 }
  38.             }
  39.         }
  40.        
  41.         public Long pop() {
  42.             if(size > 0) {
  43.                 Long k = array[0];
  44.                 array[0] = array[--size];
  45.                
  46.                 // Swim down routine
  47.                 Long temp;
  48.                 int ptr = 0;
  49.                 int max_i = ptr;
  50.                
  51.                 while(true) {
  52.                     if(left(ptr) < size && array[left(ptr)] > array[max_i]) {
  53.                         max_i = left(ptr);
  54.                     }
  55.                    
  56.                     if(right(ptr) < size && array[right(ptr)] > array[max_i]) {
  57.                         max_i = right(ptr);
  58.                     }
  59.                    
  60.                     if(ptr != max_i) {
  61.                         temp = array[ptr];
  62.                         array[ptr] = array[max_i];
  63.                         array[max_i] = temp;
  64.                         ptr = max_i;
  65.                     } else break;
  66.                 }
  67.                
  68.                 return k;
  69.             }
  70.            
  71.             return null;
  72.         }
  73.        
  74.         public int size() {
  75.             return size;
  76.         }
  77.     }
  78.    
  79.     public static void main(String[] args) {
  80.         MaxHeap heap = new MaxHeap(10);
  81.        
  82.         heap.insert(new Long(1));
  83.         heap.insert(new Long(1));
  84.         heap.insert(new Long(5));
  85.         heap.insert(new Long(129));
  86.         heap.insert(new Long(4));
  87.        
  88.         while(heap.size() > 0) {
  89.             System.out.println(heap.pop());
  90.         }
  91.     }
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top