pepcoding.com 21/10/21 medianPriorityQueue

code.cpp

#include <iostream>
#include <queue>
using namespace std;

class MedianPriorityQueue {
    public:
    priority_queue <int> left;
    priority_queue <int, vector<int>, greater<int>> right;
    
    void push(int val) {
        if(size() == 0) {
            left.push(val);
        }
        else if(left.size() > 0 && val <= left.top()) {
            left.push(val);
        }
        else {
            right.push(val);
        }
        
        // balance
        if(left.size() + 2 == right.size()) { // left is small
            left.push(right.top());
            right.pop();
        }
        else if(right.size() + 2 == left.size()) { // right is small
            right.push(left.top());
            left.pop();
        }
    }
    
    int pop() {
        if(size() == 0) {
            cout<<"Underflow"<<endl;
            return -1;
        }
        
        if(left.size() >= right.size()) {
            int top = left.top();
            left.pop();
            return top;
        }
        else {
            int top = right.top();
            right.pop();
            return top;
        }
    }
    
    int top() {
        if(size() == 0) {
            cout<<"Underflow"<<endl;
            return -1;
        }
        
        if(left.size() >= right.size()) {
            return left.top();
        }
        else {
            return right.top();
        }
    }
    
    int size() {
        return left.size() + right.size();
    }
};

int main() {
    MedianPriorityQueue pq;
    
    string str;
    cin >> str;
    while(str!="quit"){
        if(str=="add"){
            int val;
            cin >> val;
            pq.push(val);
        }
        else if(str=="remove"){
            int val = pq.pop();
            if(val != -1) {
                cout<<val<<endl;
            }
        }
        else if(str=="peek"){
            int val = pq.top();
            if(val != -1) {
                cout<<val<<endl;
            }
        }
        else if(str=="size"){
            cout<<pq.size()<<endl;
        }
        cin >> str;
    }
    
    return 0;
}

code.py

class newPriorityQueue(object):
    def __init__(self):
        self.queue = []

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    def isEmpty(self):
        return len(self.queue) == 0

    def insert(self, data):
        self.queue.append(data)

    def delete(self):
        try:
            max = 0
            for i in range(len(self.queue)):
                if self.queue[i] < self.queue[max]:
                    max = i
            item = self.queue[max]
            del self.queue[max]
            return item
        except IndexError:
            print()
            exit()
        
            
    def sz(self):
        return len(self.queue)



class PriorityQueue(object):
    def __init__(self):
        self.queue = []

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    def isEmpty(self):
        return len(self.queue) == 0
    
    def insert(self, data):
        self.queue.append(data)
   
    def delete(self):
        try:
            max = 0
            for i in range(len(self.queue)):
                if self.queue[i] > self.queue[max]:
                    max = i
            item = self.queue[max]
            del self.queue[max]
            return item
        except IndexError:
            print()
            exit()
    
    def top(self):  
        return max(self.queue)
       
            
    def sz(self):
        return len(self.queue)


def size():
    return left.sz()+right.sz()
    
def balance():
    if left.sz()+1==right.sz():
        val=right.delete()
        left.insert(val)
    elif left.sz()==right.sz()+2:
        val=left.delete()
        right.insert(val)



def add(val):
    if left.sz()==0 or val<left.top():
        left.insert(val)
    else:
        right.insert(val)
        
    balance()


    
def remove():
    if(size()==0):
        print("Underflow",end="\n")
        return -1
        
    val=left.delete()
    balance()
    return val
  

   
def peek():
    if(size()==0):
        print("Underflow",end="\n")
        return -1
        
    val=left.top()
    balance()
    return val
    


left = PriorityQueue()
right= newPriorityQueue()


while(1):
    s=input()
    if s[0]=='a':
        num=s[4:]
        val=int(num)
        add(val)
    
    elif s[0]=='r':
        val=remove()
        if val!=-1:
            print(val,end="\n")
    
    elif s[0]=='p':
        val=peek()
        if val!=-1:
            print(val,end="\n")
            
    else:
        break
   

snippet.cpp

#include <iostream>
#include <queue>
using namespace std;

class MedianPriorityQueue {
    public:
    priority_queue <int> left;
    priority_queue <int, vector<int>, greater<int>> right;
    
    void push(int val) {
       //write your code here
    }
    
    int pop() {
        //write your code here
    }
    
    int top() {
         //write your code here 
    }
    
    int size() {
          //write your code here
    }
};

int main() {
    MedianPriorityQueue pq;
    
    string str;
    cin >> str;
    while(str!="quit"){
        if(str=="add"){
            int val;
            cin >> val;
            pq.push(val);
        }
        else if(str=="remove"){
            int val = pq.pop();
            if(val != -1) {
                cout<<val<<endl;
            }
        }
        else if(str=="peek"){
            int val = pq.top();
            if(val != -1) {
                cout<<val<<endl;
            }
        }
        else if(str=="size"){
            cout<<pq.size()<<endl;
        }
        cin >> str;
    }
    
    return 0;
}

snippet.py

class newPriorityQueue(object):
    def __init__(self):
        self.queue = []

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    def isEmpty(self):
        return len(self.queue) == 0

    def insert(self, data):
        self.queue.append(data)

    def delete(self):
        try:
            max = 0
            for i in range(len(self.queue)):
                if self.queue[i] < self.queue[max]:
                    max = i
            item = self.queue[max]
            del self.queue[max]
            return item
        except IndexError:
            print()
            exit()
        
            
    def sz(self):
        return len(self.queue)



class PriorityQueue(object):
    def __init__(self):
        self.queue = []

    def __str__(self):
        return ' '.join([str(i) for i in self.queue])

    def isEmpty(self):
        return len(self.queue) == 0
    
    def insert(self, data):
        self.queue.append(data)
   
    def delete(self):
        try:
            max = 0
            for i in range(len(self.queue)):
                if self.queue[i] > self.queue[max]:
                    max = i
            item = self.queue[max]
            del self.queue[max]
            return item
        except IndexError:
            print()
            exit()
    
    def top(self):  
        return max(self.queue)
       
            
    def sz(self):
        return len(self.queue)


def size():
    #write your code here



def add(val):
    #write your code here


    
def remove():
    #write your code here
  

   
def peek():
    #write your code here
    





left = PriorityQueue()
right= newPriorityQueue()


while(1):
    s=input()
    if s[0]=='a':
        num=s[4:]
        val=int(num)
        add(val)
    
    elif s[0]=='r':
        val=remove()
        if val!=-1:
            print(val,end="\n")
    
    elif s[0]=='p':
        val=peek()
        if val!=-1:
            print(val,end="\n")
            
    else:
        break