Как эффективно отслеживать минимальное значение в скользящей матрице? [Дубликат]

Как описано в http://pandas.pydata.org/pandas-docs/stable/text.html :

df.columns = df.columns.str.replace('$','')

68
задан templatetypedef 9 May 2013 в 16:50
поделиться

12 ответов

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

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

Например, для запроса 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().

86
ответ дан Vasu 28 August 2018 в 17:24
поделиться

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

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

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

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

2
ответ дан Andy Mikula 28 August 2018 в 17:24
поделиться

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

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

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

при получении минимума A используйте переднюю часть B как возвращаемое значение.

dequeue и getmin, очевидно, O (1). Для операции enqueue рассмотрите 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])
3
ответ дан jianglai 28 August 2018 в 17:24
поделиться

Реализация 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);
        }
    }
}
0
ответ дан Nitish Bhagat 28 August 2018 в 17:24
поделиться

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

1
ответ дан Olhovsky 28 August 2018 в 17:24
поделиться

Хорошо. Я думаю, что у меня есть ответ, который дает вам все эти операции в amortized 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 & lt; 2. Затем мы изменим дерево так, чтобы оно выглядело так:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Обратите внимание, что обход по порядку дает 2 1 4 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) на элемент.

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

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

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

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

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

25
ответ дан OmarOthman 28 August 2018 в 17:24
поделиться

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

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

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

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

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

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

1
ответ дан Sandeep 28 August 2018 в 17:24
поделиться

Реализация JavaScript

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

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

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

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

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) амортизировано

< blockquote>

Для 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
*/

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

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];
  }
}

0
ответ дан Scott Rudiger 28 August 2018 в 17:24
поделиться
#include <iostream>
#include <queue>
#include <deque>
using namespace std;

queue<int> main_queue;
deque<int> min_queue;

void clearQueue(deque<int> &q)
{
  while(q.empty() == false) q.pop_front();
}

void PushRear(int elem)
{
  main_queue.push(elem);

  if(min_queue.empty() == false && elem < min_queue.front())
  {
      clearQueue(min_queue);
  }

  while(min_queue.empty() == false && elem < min_queue.back())
  {
      min_queue.pop_back();
  }

  min_queue.push_back(elem);
}

void PopFront() 
{
  int elem = main_queue.front();
  main_queue.pop();

  if (elem == min_queue.front())
  {
       min_queue.pop_front();
  }
}

int GetMin() 
{ 
  return min_queue.front(); 
}

int main()
{
  PushRear(1);
  PushRear(-1);
  PushRear(2);

  cout<<GetMin()<<endl;
  PopFront();
  PopFront();
  cout<<GetMin()<<endl;

  return 0;
}
0
ответ дан TheMan 28 August 2018 в 17:24
поделиться

Мы знаем, что push и pop являются постоянными операциями времени [O (1), чтобы быть точным].

Но когда мы думаем о get_min () [т.е. для нахождения текущего минимального числа в очереди] обычно первое, что приходит на ум, - это поиск всей очереди каждый раз, когда выполняется запрос для элемента минимума. Но это никогда не даст постоянной работы, что является главной целью проблемы.

Обычно это часто задают в интервью, поэтому вы должны знать трюк

To сделайте это, мы должны использовать еще две очереди, которые будут содержать дорожку минимального элемента, и мы должны продолжить модификацию этих двух очередей, поскольку мы выполняем операции push и pop в очереди, чтобы минимальный элемент был получен в O (1) раз.

Вот самоописательный судо-код, основанный на упомянутом выше подходе.

    Queue q, minq1, minq2;
    isMinq1Current=true;   
    void push(int a)
    {
      q.push(a);
      if(isMinq1Current)
      {
        if(minq1.empty) minq1.push(a);
        else
        {
          while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
          minq2.push(a);
          while(!minq1.empty) minq1.pop();
          isMinq1Current=false;
        }
      }
      else
      {
        //mirror if(isMinq1Current) branch. 
      }
    }

    int pop()
    { 
      int a = q.pop();
      if(isMinq1Current)
      {
        if(a==minq1.top) minq1.pop();
      }
      else
      {
        //mirror if(isMinq1Current) branch.    
      }
    return a;
    }
0
ответ дан thirtydot 28 August 2018 в 17:24
поделиться

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

Сначала нам нужны некоторые вещи, которые предоставляют push_back (), push_front (), pop_back () и pop_front () в 0 (1). Его легко реализовать с помощью массива и 2 итераторов. Первый итератор будет указывать на фронт, второй на спину. Давайте назовем такой материал 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.:)

21
ответ дан UmmaGumma 28 August 2018 в 17:24
поделиться

Это решение содержит 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
0
ответ дан user3139774 28 August 2018 в 17:24
поделиться
Другие вопросы по тегам:

Похожие вопросы: