Implementieren Sie eine queue, in die push_rear(), pop_front() und get_min() sind alle Konstanten Zeit-Operationen

Okay - ich denke ich habe eine Antwort, die Ihnen alle diese Vorgänge in fortgeführten O(1), was bedeutet, dass jeder Betrieb kann bis zu O(n), sondern eine beliebige Folge von n Operationen in O(1) Zeit pro Betrieb.

Die Idee ist, speichern Sie Ihre Daten als Kartesische Baum. Dies ist ein binärer Baum, der die Beachtung der min-heap-Eigenschaft (jeder Knoten ist nicht größer als seine Kinder) und bestellt in einer Weise, so dass ein inorder-Traversierung der Knoten gibt Sie wieder die Knoten in der gleichen Reihenfolge in der Sie Hinzugefügt wurden. Zum Beispiel, hier ist eine kartesische Struktur für die Abfolge 2 1 4 3 5:

       1
     /  \
    2      3
          /\
         4   5

Ist es möglich, fügen Sie ein element in einem kartesischen Baum in O(1) amortisiert Zeit mit dem folgenden Verfahren. Auf der rechten Wirbelsäule des Baumes (der Pfad von der Wurzel bis zum am weitesten rechts liegenden Blatt, geformt durch die immer Fuß auf der rechten Seite). Beginnend beim am weitesten rechts liegenden Knoten, Scannen Sie nach oben entlang diesem Pfad, bis Sie die ersten Knoten, die kleiner als der Knoten, den Sie sind einfügen.

Ändern, dass Knoten, so dass seine Rechte Kind wird diesen neuen Knoten, dann machen Sie, dass Knoten die ehemalige Rechte Kind das linke Kind des Knoten, den Sie gerade Hinzugefügt haben. Zum Beispiel, nehmen wir an, wir wollen, legen Sie eine weitere Kopie 2 in der oben stehenden Baum. Wir Wandern rechts der Wirbelsäule vorbei an der 5 und der 3, aber nicht unterhalb der 1, weil 1 < 2. Wir ändern dann den Baum wie folgt Aussehen:

       1
     /  \
    2      2
          /
         3
        /\
       4   5

Beachten Sie, dass ein inorder traversal gibt 2 1 4 3 5 2, das ist die Reihenfolge, in der wir Hinzugefügt die Werte.

Dieser läuft in amortisiert O(1) denn wir können eine potentielle Funktion gleich der Anzahl der Knoten im rechten Wirbelsäule des Baumes. Die Reale Zeit, die erforderlich ist, um einen Knoten einzufügen ist 1 plus die Anzahl der Knoten in der Wirbelsäule, die wir betrachten (nennen dieses k). Einmal finden wir den Ort zum einfügen der Knoten, der Größe der Wirbelsäule schrumpft durch die Länge k - 1, da jeder der k Knoten, die wir besuchten, sind nicht mehr auf der rechten Seite der Wirbelsäule, und der neue Knoten wird an seine Stelle. Dies gibt einen amortized cost 1 + k + (1 - k) = 2 = O(1), für den amortisiert O(1) einfügen. Als eine andere Art des Denkens über diese, sobald ein Knoten verschoben wurde aus dem rechts der Wirbelsäule, es ist nie Teil der rechten Wirbelsäule wieder, und so werden wir nie haben, um es zu verschieben wieder. Da jeder der n Knoten kann verschoben werden, höchstens einmal, das bedeutet, dass n-Insertionen tun können, bei den meisten n bewegt, so dass die Gesamt-Laufzeit ist höchstens O(n) für ein amortisiert O(1) pro element.

Tun dequeue Schritt, wir entfernen Sie einfach die am weitesten Links stehende Knoten aus der kartesische Baum. Wenn dieser Knoten ein Blatt ist, sind wir fertig. Ansonsten kann der Knoten nur ein Kind hat (das Rechte Kind), und so ersetzen wir den Knoten mit seinem rechten Kind. Vorausgesetzt, dass wir verfolgen, wo der Knoten ganz Links ist, ist dieser Schritt dauert O(1) Zeit. Jedoch nach dem entfernen der Knoten ganz Links und ersetzen Sie es mit dem rechten Kind, könnten wir nicht wissen, wo der neue Knoten ganz Links ist. Um dies zu beheben, wir gehen einfach die Links der Wirbelsäule von dem Baum ab, an den neuen Knoten wir gerade umgezogen, um die am weitesten Links stehende Kind. Ich behaupte, dass dieser noch läuft in O(1) amortisiert Zeit. Um dies zu sehen, ich behaupte, dass ein Knoten besucht wird höchstens einmal in einer dieser Pässe zu finden, die am weitesten Links stehende Knoten. Um dies zu sehen, beachten Sie, dass sobald ein Knoten besucht wurde dieser Weg, der einzige Weg, dass wir jemals benötigen könnte, um es zu betrachten wieder sein würde, wenn es waren bewegt von einem Kind der Knoten ganz Links zu den Knoten ganz Links. Aber alle Knoten besucht sind die Eltern von der ganz Links liegenden Knoten, so kann dies nicht passieren. Folglich kann jeder Knoten besucht wird höchstens einmal während dieses Prozesses, und die pop läuft in O(1).

Können wir tun, finden-min in O(1) da die kartesischen Baum gibt uns Zugriff auf das kleinste element des Baums zum Nulltarif; es ist die Wurzel des Baumes.

Schließlich, um zu sehen, dass die Knoten wieder in der gleichen Reihenfolge, in der Sie eingefügt wurden, beachten Sie, dass eine Kartesisches Struktur immer speichert seine Elemente, so dass ein inorder-Traversierung besucht Sie in sortierter Reihenfolge. Da wir immer entfernen Sie die Knoten ganz Links bei jedem Schritt, und dies ist das erste element der inorder-Traversierung, wir haben immer die Knoten in der Reihenfolge, in der Sie eingegeben wurden.

Kurz gesagt, erhalten wir O(1) amortisiert push-und pop -, und O(1) worst-case-finden-min.

Ob ich kommen kann, mit worst-case O(1) Implementierung, ich werde auf jeden Fall posten. Dies war ein großes problem; vielen Dank für die Veröffentlichung!

InformationsquelleAutor templatetypedef

Verwenden Sie eine deque (A) zum speichern der Elemente und andere deque (B) zum speichern der minima.

Wenn x in die Warteschlange eingereiht, push_back es zu Ein und halten pop_backing B, bis der Rücken von B ist kleiner als x, dann push_back x B.

beim abarbeiten der Warteschlange Ein, pop_front Eine als Rückgabewert, und wenn es gleich an der Vorderseite des B, pop_front B als gut.

bekommen, wenn die mindestens Eine, der vorderen von B als Rückgabewert.

dequeue und getmin sind offensichtlich O(1). Für den enqueue-operation, sollten die push_back von n Elementen. Es gibt n push_back A, n push_back zu B und bei den meisten n pop_back von B, weil jedes element bleiben entweder in B oder knallte einmal aus B., Über alle gibt es O(3n) Operationen und damit die amortisierten Kosten O(1) als auch für enqueue.

Schließlich der Grund, warum dieser Algorithmus funktioniert, ist, dass, wenn Sie enqueue x zu A, wenn es Elemente in B, die größer sind als x, wird er sich nie minima jetzt, weil x bleibt in der Warteschlange länger ist als alle Elemente in B (eine queue ist FIFO). Deshalb brauchen wir, um pop-out-Elementen in B (von hinten), die größer sind als x vor drücken wir x in 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])

InformationsquelleAutor jianglai

Lösungen zu dieser Frage, einschließlich der code, kann hier gefunden werden:
http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

InformationsquelleAutor Olhovsky

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

InformationsquelleAutor TheMan

Java-Implementierung

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

InformationsquelleAutor Nitish Bhagat