daily pastebin goal
64%
SHARE
TWEET

Untitled

a guest Jan 19th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Text;
  3. class MaxHeap{
  4.     private int[] ar;
  5.     private int count;
  6.     public StringBuilder sb;
  7.     public MaxHeap(){
  8.         ar = new int[150000];
  9.         count = 0;
  10.         sb = new StringBuilder("");
  11.     }
  12.     private int left(int i){
  13.         return 2*i + 1;
  14.     }
  15.     private int right(int i){
  16.         return 2*i + 2;
  17.     }
  18.     private int parent(int i){
  19.         return (i-1)/2;
  20.     }
  21.     public void insert(int n){
  22.         count++;
  23.         int i = count-1;
  24.         ar[i] = n;
  25.         percolateUp(count-1);
  26.     }
  27.     private void percolateUp(int i){
  28.         if(i <= 0){
  29.             return;
  30.         }
  31.         if(ar[i] > ar[parent(i)]){
  32.             int temp = ar[i];
  33.             ar[i] = ar[parent(i)];
  34.             ar[parent(i)] = temp;
  35.             percolateUp(parent(i));
  36.         }
  37.     }
  38.     private void percolateDown(int i){
  39.         int l = left(i);
  40.         int r = right(i);
  41.         int max = i;
  42.         bool flag = false;
  43.         if(l < count && ar[i] < ar[l]){
  44.             max = l;
  45.             flag = true;
  46.         }
  47.         if(r < count && ar[r] > ar[max]){
  48.             max = r;
  49.             flag = true;
  50.         }
  51.         if(flag){
  52.             int temp = ar[i];
  53.             ar[i] = ar[max];
  54.             ar[max] = temp;
  55.             percolateDown(max);
  56.         }
  57.     }
  58.     public void deleteMax(){
  59.         if(count == 0){
  60.             return;
  61.         }
  62.         if(count == 1){
  63.             count--;
  64.             return;
  65.         }
  66.         ar[0] = ar[count-1];
  67.         count--;
  68.         percolateDown(0);
  69.     }
  70.     public string getMax(){
  71.         if(count <= 0){
  72.             return "Empty";
  73.         }
  74.         return ar[0].ToString();
  75.     }
  76.     public void process(string str){
  77.         string[] s = str.Split(' ');
  78.         if(s[0].Equals("getMax")){
  79.             Console.WriteLine(getMax());
  80.         }
  81.         else if(s[0].Equals("delMax")){
  82.             deleteMax();
  83.         }
  84.         else if(s[0].Equals("insert")){
  85.             insert(Convert.ToInt32(s[1]));
  86.         }
  87.     }
  88.     public static void Main(string[] args){
  89.         MaxHeap ob = new MaxHeap();
  90.         for(int i=0;i<100;i++){
  91.             ob.insert(i+1);
  92.         }
  93.         for(int i=0;i<100;i++){
  94.             Console.WriteLine(ob.getMax());
  95.             ob.deleteMax();
  96.         }
  97.     }
  98. }
RAW Paste Data
Top