Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Text;
- class MaxHeap{
- private int[] ar;
- private int count;
- public StringBuilder sb;
- public MaxHeap(){
- ar = new int[150000];
- count = 0;
- sb = new StringBuilder("");
- }
- private int left(int i){
- return 2*i + 1;
- }
- private int right(int i){
- return 2*i + 2;
- }
- private int parent(int i){
- return (i-1)/2;
- }
- public void insert(int n){
- count++;
- int i = count-1;
- ar[i] = n;
- percolateUp(count-1);
- }
- private void percolateUp(int i){
- if(i <= 0){
- return;
- }
- if(ar[i] > ar[parent(i)]){
- int temp = ar[i];
- ar[i] = ar[parent(i)];
- ar[parent(i)] = temp;
- percolateUp(parent(i));
- }
- }
- private void percolateDown(int i){
- int l = left(i);
- int r = right(i);
- int max = i;
- bool flag = false;
- if(l < count && ar[i] < ar[l]){
- max = l;
- flag = true;
- }
- if(r < count && ar[r] > ar[max]){
- max = r;
- flag = true;
- }
- if(flag){
- int temp = ar[i];
- ar[i] = ar[max];
- ar[max] = temp;
- percolateDown(max);
- }
- }
- public void deleteMax(){
- if(count == 0){
- return;
- }
- if(count == 1){
- count--;
- return;
- }
- ar[0] = ar[count-1];
- count--;
- percolateDown(0);
- }
- public string getMax(){
- if(count <= 0){
- return "Empty";
- }
- return ar[0].ToString();
- }
- public void process(string str){
- string[] s = str.Split(' ');
- if(s[0].Equals("getMax")){
- Console.WriteLine(getMax());
- }
- else if(s[0].Equals("delMax")){
- deleteMax();
- }
- else if(s[0].Equals("insert")){
- insert(Convert.ToInt32(s[1]));
- }
- }
- public static void Main(string[] args){
- MaxHeap ob = new MaxHeap();
- for(int i=0;i<100;i++){
- ob.insert(i+1);
- }
- for(int i=0;i<100;i++){
- Console.WriteLine(ob.getMax());
- ob.deleteMax();
- }
- }
- }
Add Comment
Please, Sign In to add comment