Реализуйте очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем

Question

Я сталкивался с таким вопросом: Реализовать очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем.

Сначала я подумал об использовании min- структура данных кучи, которая имеет сложность O (1) для get_min ().Но push_rear () и pop_front () были бы O (log (n)).

Кто-нибудь знает, что было бы лучшим способом реализовать такую ​​очередь, которая имеет O (1) push (), pop () и min ()?

Я гуглил об этом и хотел указать на этот поток Алгоритм вундеркиндов .Но похоже, что ни одно из решений не следует правилу постоянного времени для всех трех методов: push (), pop () и min ().

Спасибо за все предложения.

Answer 1

Вы можете реализовать стек с O (1) pop (), push () и get_min (): просто сохраните текущий минимум вместе с каждым элементом. Так, например, стек [4,2,5,1] (1 сверху) становится [(4,4), (2,2), (5,2), (1,1)].

Тогда вы можете использовать два стека для реализации очереди . Нажмите на один стек, поп от другого; если второй стек пуст во время всплывающего окна, переместите все элементы из первого стека во второй.

E.g для запроса pop, при перемещении всех элементов из первого стека [(4,4), (2,2), (5,2), (1,1)], второй стек будет [(1,1), (5,1), (2,1), (4,1)]. и теперь возвращаем верхний элемент из второго стека.

Чтобы найти минимальный элемент очереди, посмотрите на наименьшие два элемента отдельных минимальных стеков, а затем возьмите минимум из этих двух значений. (Конечно, здесь есть некоторая дополнительная логика, если один из стеков пуст, но это не так уж сложно обойти).

Он будет иметь O (1) get_min() и push() и амортизированный O (1) pop().

Answer 2

Хорошо - я думаю, что у меня есть ответ, который дает вам все эти операции в амортизированном O (1), что означает, что любая операция может занять до O (n), но любая последовательность из nОперации занимают O (1) раз за операцию .

Идея состоит в том, чтобы хранить ваши данные как декартово дерево .Это двоичное дерево, подчиняющееся свойству min-heap (каждый узел не больше его дочерних элементов) и упорядочено таким образом, что обход узлов по порядку возвращает вам узлы в том же порядке, в котором они были добавлены.Например, вот декартово дерево для последовательности 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

Можно вставить элемент в декартово дерево за O (1) амортизированного времени, используя следующую процедуру.Посмотрите на правый корешок дерева (путь от корня до самого правого листа, образуемого всегда гуляющим направо).Начиная с самого правого узла, сканируйте вверх по этому пути, пока не найдете первый узел, меньший, чем узел, который вы вставляете.
Измените этот узел так, чтобы его правый дочерний узел был этим новым узлом, а затем сделайте прежний правый дочерний узел этого узла левымдочерний элемент узла, который вы только что добавили.Например, предположим, что мы хотим вставить еще одну копию 2 в вышеприведенное дерево.Мы идем вверх по правому отделу позвоночника мимо 5 и 3, но останавливаемся ниже 1, потому что 1 <2. Затем мы меняем дерево так: </p>

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Обратите внимание, что обход по порядку дает 2 14 3 5 2, то есть последовательность, в которой мы добавили значения.

Это выполняется в амортизированной O (1), потому что мы можем создать потенциальную функцию, равную количеству узлов в правой части дерева,Реальное время, необходимое для вставки узла, равно 1 плюс количество узлов в позвоночнике, которое мы рассматриваем (назовите это k).Как только мы находим место для вставки узла, размер позвоночника уменьшается на длину k - 1, поскольку каждый из k узлов, которые мы посетили, больше не находится на правом позвоночнике, а новый узел находится на своем месте.Это дает амортизированную стоимость 1 + k + (1 - k) = 2 = O (1) для амортизированной вставки O (1).В качестве другого способа думать об этом, когда узел перемещен с правого отдела позвоночника, он больше никогда не является частью правого отдела позвоночника, и поэтому нам больше никогда не придется его перемещать.Поскольку каждый из n узлов может быть перемещен не более одного раза, это означает, что n вставок может выполнить не более n перемещений, поэтому общее время выполнения составляет не более O (n) для амортизированного O (1) на элемент.

Чтобы сделать шаг удаления, мы просто удаляем самый левый узел из декартового дерева.Если этот узел является листом, мы закончили.В противном случае у узла может быть только один дочерний элемент (правильный дочерний элемент), поэтому мы заменяем узел его правым дочерним элементом.При условии, что мы отслеживаем, где находится самый левый узел, этот шаг занимает O (1) времени.Однако после удаления самого левого узла и замены его правым дочерним узлом мы можем не знать, где находится новый самый левый узел.Чтобы это исправить, мы просто идем по левому позвоночнику дерева, начиная с нового узла, который мы только что переместили к самому левому дочернему элементу.Я утверждаю, что это все еще работает в O (1) амортизированное время.Чтобы увидеть это, я утверждаю, что узел посещается не более одного раза в течение любого из этих проходов, чтобы найти самый левый узел.Чтобы увидеть это, обратите внимание, что после того, как узел был посещен таким образом, единственный способ, которым нам когда-либо понадобится посмотреть на него снова, будет, если он будет перемещен из дочернего элемента самого левого узла в крайний левый узел.Но все посещенные узлы являются родителями самого левого узла, поэтому этого не может быть.Следовательно, каждый узел посещается не более одного раза во время этого процесса, и всплывающее окно выполняется в O (1).

Мы можем сделать find-min в O (1), потому что декартово дерево дает нам доступ к наименьшемуэлемент дерева бесплатно;это корень дерева.

Наконец, чтобы увидеть, что узлы возвращаются в том же порядке, в котором они были вставлены, обратите внимание, что декартово дерево всегда хранит свои элементы, так что обход по порядку посещает их в отсортированном порядке. Так как мы всегда удаляем самый левый узел на каждом шаге, и это первый элемент обхода inorder, мы всегда возвращаем узлы в том порядке, в котором они были вставлены.

Короче говоря, мы получаем O (1) амортизированных push и pop, и O (1) find-min худшего случая.

Если я смогу предложить реализацию O (1) в худшем случае, я обязательно опубликую ее. Это была большая проблема; спасибо за публикацию!

Answer 3

Хорошо, вот одно из решений.

Сначала нам понадобятся некоторые вещи, которые обеспечивают push_back (), push_front (), pop_back () и pop_front () в 0 (1).Это легко реализовать с помощью массива и двух итераторов.Первый итератор будет указывать на фронт, второй на тыл.Давайте назовем такие вещи deque.

Вот псевдокод:

class MyQueue//Our data structure
{
    deque D;//We need 2 deque objects
    deque Min;

    push(element)//pushing element to MyQueue
    {
        D.push_back(element);
        while(Min.is_not_empty() and Min.back()>element)
             Min.pop_back();
        Min.push_back(element);
    }
    pop()//poping MyQueue
    {
         if(Min.front()==D.front() )
            Min.pop_front();
         D.pop_front();
    }

    min()
    {
         return Min.front();
    }
}

Объяснение:

Пример давайте нажмем цифры [12,5,10,7,11,19] и нашему MyQueue

1) нажатие 12

D [12]
Min[12]

2) нажатие 5

D[12,5]
Min[5] //5>12 so 12 removed

3) нажатие 10

D[12,5,10]
Min[5,10]

4) нажатие 7

D[12,5,10,7]
Min[5,7]

6) нажатие 11

D[12,5,10,7,11]
Min[5,7,11]

7) нажатие 19

D[12,5,10,7,11,19]
Min[5,7,11,19]

Теперь давайте вызовем pop_front()

мы получили

 D[5,10,7,11,19]
 Min[5,7,11,19]

Минимум 5

Давайте снова вызовем pop_front ()

Объяснение: pop_front удалит 5 из D,но перед ним также появится передний элемент Min, потому что он равен переднему элементу D. (5).

 D[10,7,11,19]
 Min[7,11,19]

И минимум 7.:)

Answer 4

Используйте одну деку (A) для хранения элементов и другую деку (B) для хранения минимумов.

Когда x ставится в очередь, переместите его обратно к A и продолжайте pop_backing B, пока задняя часть B не станет меньше x, затем переместите назад x к B.

при удалении из очереди A, pop_front A в качестве возвращаемого значения, а если оно равно фронту B, также pop_front B.

при получении минимума A, используйте фронт B в качестве возвращаемого значения.

dequeue и getmin - это, очевидно, O (1). Для операции постановки в очередь рассмотрим push_back из n элементов. Существует n push_back для A, n push_back для B и не более n pop_back для B, потому что каждый элемент либо останется в B, либо будет извлечен один раз из B. В целом существует O (3n) операций, и поэтому амортизированная стоимость равна O (1) а также для постановки в очередь.

Наконец, причина того, что этот алгоритм работает, состоит в том, что когда вы ставите x в очередь A, если в B есть элементы, которые больше x, они никогда не будут минимальными, потому что x будет оставаться в очереди A дольше, чем любые элементы в B (очередь FIFO). Поэтому нам нужно выдвинуть элементы в B (сзади), которые больше, чем x, прежде чем мы введем x в B.

from collections import deque


class MinQueue(deque):
    def __init__(self):
        deque.__init__(self)
        self.minq = deque()

    def push_rear(self, x):
        self.append(x)
        while len(self.minq) > 0 and self.minq[-1] > x:
            self.minq.pop()
        self.minq.append(x)

    def pop_front(self):
        x = self.popleft()
        if self.minq[0] == x:
            self.minq.popleft()
        return(x)

    def get_min(self):
        return(self.minq[0])

Answer 5

На самом деле вы можете использовать LinkedList для обслуживания очереди.

Каждый элемент в LinkedList будет иметь тип

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

У вас может быть два указателя: один указывает на старт, а другой - на другой.указывает на конец.

Если вы добавляете элемент в начало очереди.Изучите указатель начала и узел для вставки.Если узел для вставки currentmin меньше, чем запуск узла currentmin, для вставки currentmin это минимум.Иначе обновите currentmin с помощью start currentmin.

Повторите то же самое для enque.

Answer 6

Решения этого вопроса, включая код, можно найти здесь: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

Answer 7

Если вы не возражаете против хранения дополнительных данных, хранить минимальное значение будет тривиально.Push и pop могут обновить значение, если новый или удаленный элемент является минимальным, и возвращение минимального значения так же просто, как получение значения переменной.

Это предполагает, что get_min () не изменяетданные;если вы предпочитаете что-то вроде pop_min () (т.е. удалите минимальный элемент), вы можете просто сохранить указатель на фактический элемент и предшествующий ему элемент (если есть) и обновить их соответственно с помощью push_rear () и pop_front ()а также.

Редактировать после комментариев:

Очевидно, что это приводит к O (n) push и pop в случае, если минимум этих операций изменяется, и поэтомуне строго соответствуют требованиям.

Answer 8

Реализация JavaScript

(Благодарим за решение adamax за идею; I свободно на основе реализации. Перейти к основанию, чтобы увидеть полностью прокомментированный код или прочитать через общие шаги, приведенные ниже. Обратите внимание, что это находит максимальное значение в постоянное время O (1), а не минимальное значение - легко изменить):

Общая идея заключается в создании двух стеков при построении MaxQueue (я использовал связанный список в качестве базовой структуры данных Stack - не включен в код; но любой Stack будет работать до тех пор, пока это реализовано с O (1) вставкой / удалением). Один будет в основном pop от (dqStack), а другой - от push до (eqStack).

---

Вставка: O (1) худший случай

Для enqueue, если MaxQueue пусто, мы push примем значение dqStack вместе с текущим максимальным значением в кортеже (то же самое значение, поскольку единственное значение в MaxQueue); e.g.:

const m = new MaxQueue();

m.enqueue(6);

/*
the dqStack now looks like:
[6, 6] - [value, max]
*/

Если MaxQueue не пусто, мы push просто значение до eqStack;

m.enqueue(7);
m.enqueue(8);

/*
dqStack:         eqStack: 8
         [6, 6]           7 - just the value
*/

Затем обновите максимальное значение в кортеже.

/*
dqStack:         eqStack: 8
         [6, 8]           7
*/

---

Удаление: O (1) амортизировано

Для dequeue мы pop из dqStack и вернем значение из кортежа.

m.dequeue();
> 6

// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/

Затем, если dqStack пусто, переместите все значения в eqStack в dqStack, например ::

// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);

/*
the stacks will look like:

dqStack:         eqStack: 1
                          4
                          2
         [3, 5]           5
*/

По мере перемещения каждого значения мы будем проверять, превышает ли оно максимальное значение на данный момент , и сохраняем его в каждом кортеже:

maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3

// as dequeue moves one value over, it checks if it's greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update                          eqStack:
         [2, 4] => 2 < 4 - no update                         
         [4, 4] => 4 > 1 - update                            
         [1, 1] => 1st value moved over so max is itself            empty
*/

Поскольку каждое значение перемещается в dqStack самое большее один раз , мы можем сказать, что dequeue имеет O (1) амортизированную сложность времени.

---

Нахождение максимального значения: O (1) наихудший случай

Затем в любой момент времени мы можем вызвать getMax, чтобы получить текущее максимальное значение в O (1) постоянном времени. Пока MaxQueue не пусто, максимальное значение легко выводится из следующего кортежа в dqStack.

maxQ.getMax();
> 5

// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/

---

Код

class MaxQueue {
  constructor(...data) {
    // create a dequeue Stack from which we'll pop
    this.dqStack = new Stack();
    // create an enqueue Stack to which we'll push
    this.eqStack = new Stack();
    // if enqueueing data at construction, iterate through data and enqueue each
    if (data.length) for (const datum of data) this.enqueue(datum);
  }
  enqueue(data) { // O(1) constant insertion time
    // if the MaxQueue is empty,
    if (!this.peek()) {
      // push data to the dequeue Stack and indicate it's the max;
      this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
    } else {
      // otherwise, the MaxQueue is not empty; push data to enqueue Stack
      this.eqStack.push(data);
      // save a reference to the tuple that's next in line to be dequeued
      const next = this.dqStack.peek();
      // if the enqueueing data is > the max in that tuple, update it
      if (data > next[1]) next[1] = data;
    }
  }
  moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
    // start max at -Infinity for comparison with the first value
    let max = -Infinity;
    // until enqueue Stack is empty,
    while (this.eqStack.peek()) {
      // pop from enqueue Stack and save its data
      const data = this.eqStack.pop();
      // if data is > max, set max to data
      if (data > max) max = data;
      // push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
      this.dqStack.push([data, max]);
    }
  }
  dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // pop from the dequeue Stack and save it's data
    const [data] = this.dqStack.pop();
    // if there's no data left in dequeue Stack, move all data from enqueue Stack
    if (!this.dqStack.peek()) this.moveAllFromEqToDq();
    // return the data
    return data;
  }
  peek() { // O(1) constant peek time
    // if the MaxQueue is empty, return undefined
    if (!this.dqStack.peek()) return;
    // peek at dequeue Stack and return its data
    return this.dqStack.peek()[0];
  }
  getMax() { // O(1) constant time to find maximum value
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // peek at dequeue Stack and return the current max
    return this.dqStack.peek()[1];
  }
}

Answer 9

Реализация Java

import java.io.*;
import java.util.*;

public class queueMin {
    static class stack {

        private Node<Integer> head;

        public void push(int data) {
            Node<Integer> newNode = new Node<Integer>(data);
            if(null == head) {
                head = newNode;
            } else {
                Node<Integer> prev = head;
                head = newNode;
                head.setNext(prev);
            }
        }

        public int pop() {
            int data = -1;
            if(null == head){
                System.out.println("Error Nothing to pop");
            } else {
                data = head.getData();
                head = head.getNext();
            }

            return data;
        }

        public int peek(){
            if(null == head){
                System.out.println("Error Nothing to pop");
                return -1;
            } else {
                return head.getData();
            }
        }

        public boolean isEmpty(){
            return null == head;
        }
    }

    static class stackMin extends stack {
        private stack s2;

        public stackMin(){
            s2 = new stack();
        }

        public void push(int data){
            if(data <= getMin()){
                s2.push(data);
            }

            super.push(data);
        }

        public int pop(){
            int value = super.pop();
            if(value == getMin()) {
                s2.pop();
            }
            return value;
        }

        public int getMin(){
            if(s2.isEmpty()) {
                return Integer.MAX_VALUE;
            }
            return s2.peek();
        }
    }

     static class Queue {

        private stackMin s1, s2;

        public Queue(){
            s1 = new stackMin();
            s2 = new stackMin();
        }

        public  void enQueue(int data) {
            s1.push(data);
        }

        public  int deQueue() {
            if(s2.isEmpty()) {
                while(!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }

            return s2.pop();
        }

        public int getMin(){
            return Math.min(s1.isEmpty() ? Integer.MAX_VALUE : s1.getMin(), s2.isEmpty() ? Integer.MAX_VALUE : s2.getMin());
        }

    }



   static class Node<T> {
        private T data;
        private T min;
        private Node<T> next;

        public Node(T data){
            this.data = data;
            this.next = null;
        }


        public void setNext(Node<T> next){
            this.next = next;
        }

        public T getData(){
            return this.data;
        }

        public Node<T> getNext(){
            return this.next;
        }

        public void setMin(T min){
            this.min = min;
        }

        public T getMin(){
            return this.min;
        }
    }

    public static void main(String args[]){
       try {
           FastScanner in = newInput();
           PrintWriter out = newOutput();
          // System.out.println(out);
           Queue q = new Queue();
           int t = in.nextInt();
           while(t-- > 0) {
               String[] inp = in.nextLine().split(" ");
               switch (inp[0]) {
                   case "+":
                       q.enQueue(Integer.parseInt(inp[1]));
                       break;
                   case "-":
                       q.deQueue();
                       break;
                   case "?":
                       out.println(q.getMin());
                   default:
                       break;
               }
           }
           out.flush();
           out.close();

       } catch(IOException e){
          e.printStackTrace();
       }
    }

    static class FastScanner {
        static BufferedReader br;
        static StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDoulbe() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner newInput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new FastScanner(new File("input.txt"));
        } else {
            return new FastScanner(System.in);
        }
    }
    static PrintWriter newOutput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new PrintWriter("output.txt");
        } else {
            return new PrintWriter(System.out);
        }
    }
}

Answer 10

Это решение содержит 2 очереди:
1. main_q - сохраняет введенные числа.
2. min_q - хранит минимальные числа по определенным правилам, которые мы описали (появляются в функциях MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).

Вот код на Python. Очередь реализована с использованием списка.
Основная идея заключается в функциях MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Одним из ключевых предположений является то, что очистка очереди занимает o (0).
Тест предоставляется в конце.

import numbers

class EmptyQueueException(Exception):
    pass

class BaseQ():
    def __init__(self):
        self.l = list()

    def enqueue(self, x):
        assert isinstance(x, numbers.Number)
        self.l.append(x)

    def dequeue(self):
        return self.l.pop(0)

    def peek_first(self):
        return self.l[0]

    def peek_last(self):
        return self.l[len(self.l)-1]

    def empty(self):
        return self.l==None or len(self.l)==0

    def clear(self):
        self.l=[]

class MainQ(BaseQ):
    def __init__(self, min_q):
        super().__init__()
        self.min_q = min_q

    def enqueue(self, x):
        super().enqueue(x)
        if self.min_q.empty():
            self.min_q.enqueue(x)
        elif x > self.min_q.peek_last():
            self.min_q.enqueue(x)
        else: # x <= self.min_q.peek_last():
            self.min_q.clear()
            self.min_q.enqueue(x)

    def dequeue(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty")
        x = super().dequeue()
        if x == self.min_q.peek_first():
            self.min_q.dequeue()
        return x

    def get_min(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty, NO minimum")
        return self.min_q.peek_first()

INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
              ("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
              ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))

if __name__ == '__main__':
    min_q = BaseQ()
    main_q = MainQ(min_q)

    try:
        for operator, i in INPUT_NUMS:
            if operator=="+":
                main_q.enqueue(i)
                print("Added {} ; Min is: {}".format(i,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
            else:
                x = main_q.dequeue()
                print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
    except Exception as e:
        print("exception: {}".format(e))

Результат вышеприведенного теста:

"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum

Process finished with exit code 0