push_rear (), pop_front () 및 get_min ()이 모두 일정한 시간 작업 인 대기열을 구현합니다.
이 질문 을 보았습니다. push_rear (), pop_front () 및 get_min ()이 모두 일정한 시간 작업 인 대기열을 구현하십시오.
처음에는 get_min ()에 대해 O (1) 복잡성을 갖는 최소 힙 데이터 구조를 사용하는 것을 생각했습니다. 그러나 push_rear () 및 pop_front ()는 O (log (n))입니다.
누구든지 O (1) push (), pop () 및 min ()이있는 큐를 구현하는 가장 좋은 방법이 무엇인지 알고 있습니까?
나는 이것에 대해 봤고이 Algorithm Geeks 스레드 를 지적하고 싶었습니다 . 그러나 어떤 솔루션도 push (), pop () 및 min ()의 세 가지 방법 모두에 대해 일정한 시간 규칙을 따르지 않는 것 같습니다.
모든 제안에 감사드립니다.
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().
좋아요-저는이 모든 작업을 상각 된 O (1)로 제공하는 답을 가지고 있다고 생각합니다 . 즉, 하나의 작업이 최대 O (n)까지 걸릴 수 있지만 n 작업의 시퀀스는 작업 당 O (1) 시간이 걸립니다. .
아이디어는 데이터를 데카르트 트리 로 저장하는 것 입니다 . 이것은 min-heap 속성 (각 노드가 자식보다 크지 않음)을 따르는 이진 트리이며 노드의 inorder traversal이 추가 된 것과 동일한 순서로 노드를 되돌려주는 방식으로 정렬됩니다. 예를 들어, 다음은 시퀀스에 대한 데카르트 트리입니다 2 1 4 3 5.
1
/ \
2 3
/ \
4 5
다음 절차를 사용하여 O (1) 상각 시간의 데카르트 트리에 요소를 삽입 할 수 있습니다. 나무의 오른쪽 척추 (항상 오른쪽으로 걸어 가면서 형성된 뿌리에서 가장 오른쪽 잎까지의 경로)를보십시오. 맨 오른쪽 노드에서 시작하여 삽입하는 노드보다 작은 첫 번째 노드를 찾을 때까지이 경로를 따라 위쪽으로 스캔합니다.
오른쪽 자식이이 새 노드가되도록 해당 노드를 변경 한 다음 해당 노드의 이전 오른쪽 자식을 방금 추가 한 노드의 왼쪽 자식으로 만듭니다. 예를 들어, 위의 트리에 2의 또 다른 사본을 삽입한다고 가정합니다. 5와 3을지나 오른쪽 척추를 올라가지 만 1 <2이기 때문에 1 아래에서 멈 춥니 다. 그런 다음 나무를 다음과 같이 변경합니다.
1
/ \
2 2
/
3
/ \
4 5
inorder traversal은 우리가 값을 추가 한 순서 인 2 1 4 3 5 2를 제공합니다.
이것은 트리의 오른쪽 척추에있는 노드 수와 동일한 잠재적 함수를 만들 수 있기 때문에 상각 된 O (1)에서 실행됩니다. 노드를 삽입하는 데 필요한 실시간은 1에 우리가 고려하는 척추의 노드 수를 더한 것입니다 (이것을 k라고 함). 노드를 삽입 할 위치를 찾으면 방문한 k 노드가 더 이상 오른쪽 척추에 있지 않고 새 노드가 그 자리에 있기 때문에 척추의 크기가 길이 k-1만큼 줄어 듭니다. 이것은 상각 된 O (1) 삽입물에 대해 1 + k + (1-k) = 2 = O (1)의 상각 된 비용을 제공합니다. 이것에 대한 또 다른 생각으로, 노드가 오른쪽 척추에서 이동되면 다시는 오른쪽 척추의 일부가 아니므로 다시는 이동할 필요가 없습니다. n 개의 노드는 각각 최대 한 번만 이동할 수 있으므로 n 개의 삽입이 최대 n 개의 이동을 수행 할 수 있음을 의미합니다.
대기열에서 빼기 단계를 수행하려면 데카르트 트리에서 가장 왼쪽 노드를 제거하기 만하면됩니다. 이 노드가 리프이면 완료된 것입니다. 그렇지 않으면 노드는 하나의 자식 (오른쪽 자식) 만 가질 수 있으므로 노드를 오른쪽 자식으로 바꿉니다. 가장 왼쪽 노드가 어디에 있는지 추적한다면이 단계는 O (1) 시간이 걸립니다. 그러나 가장 왼쪽 노드를 제거하고 오른쪽 자식 노드로 교체 한 후에는 새 가장 왼쪽 노드가 어디에 있는지 모를 수 있습니다. 이 문제를 해결하기 위해 방금 가장 왼쪽 자식으로 이동 한 새 노드에서 시작하여 트리의 왼쪽 척추를 따라 내려갑니다. 나는 이것이 여전히 O (1) 상환 시간 내에 실행된다고 주장합니다. 이를 확인하기 위해 가장 왼쪽 노드를 찾기 위해 이러한 패스 중 하나를 수행하는 동안 최대 한 번 노드를 방문한다고 주장합니다. 이를 확인하려면 노드가이 방법으로 방문한 후 다시 볼 필요가있는 유일한 방법은 가장 왼쪽 노드의 자식에서 가장 왼쪽 노드로 이동하는 것입니다. 그러나 방문한 모든 노드는 가장 왼쪽 노드의 부모이므로 이런 일이 발생할 수 없습니다. 결과적으로 각 노드는이 프로세스 동안 최대 한 번 방문하고 팝은 O (1)에서 실행됩니다.
데카르트 트리가 트리의 가장 작은 요소에 무료로 액세스 할 수 있기 때문에 O (1)에서 find-min을 수행 할 수 있습니다. 그것은 나무의 뿌리입니다.
마지막으로 노드가 삽입 된 순서대로 돌아 오는지 확인하기 위해 데카르트 트리는 항상 요소를 저장하여 inorder traversal이 정렬 된 순서로 방문하도록합니다. 우리는 항상 각 단계에서 가장 왼쪽 노드를 제거하고 이것이 inorder traversal의 첫 번째 요소이기 때문에, 우리는 항상 삽입 된 순서대로 다시 노드를 가져옵니다.
요컨대, 우리는 O (1) 상각 푸시 및 팝과 O (1) 최악의 경우 찾기 분을 얻습니다.
최악의 경우 O (1) 구현을 생각 해낼 수 있다면 확실히 게시 할 것입니다. 이것은 큰 문제였습니다. 게시 해 주셔서 감사합니다!
좋아, 여기에 하나의 해결책이 있습니다.
먼저 0 (1)에서 push_back (), push_front (), pop_back () 및 pop_front ()를 제공하는 것이 필요합니다. 배열 및 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는 D에서 5를 제거하지만, D의 앞 요소 (5)와 같기 때문에 Min의 앞 요소도 팝합니다.
D[10,7,11,19]
Min[7,11,19]
그리고 최소값은 7입니다. :)
하나의 데크 (A)를 사용하여 요소를 저장하고 다른 데크 (B)를 사용하여 최소값을 저장합니다.
x가 대기열에 추가되면 A로 push_back하고 B의 뒷면이 x보다 작을 때까지 B를 계속 pop_backing 한 다음 x를 B로 push_back합니다.
A, pop_front A를 반환 값으로 빼고 B의 앞면과 같으면 pop_front B도 마찬가지입니다.
A의 최소값을 구할 때 B의 앞을 반환 값으로 사용하십시오.
dequeue와 getmin은 분명히 O (1)입니다. 대기열에 넣기 작업의 경우 n 요소의 push_back을 고려하십시오. A에 대한 n 개의 push_back, B에 대한 n 개의 push_back 및 B에 대한 최대 n 개의 pop_back이 있습니다. 각 요소는 B에 머물거나 B에서 한 번 튀어 나오기 때문입니다. (1) 또한 대기열에 넣습니다.
마지막으로이 알고리즘이 작동하는 이유는 x를 A에 넣을 때 B에 x보다 큰 요소가 있으면 x가 B (큐 FIFO입니다). 따라서 우리는 x를 B에 밀어 넣기 전에 B의 (뒤에서) x보다 큰 요소를 튀어 나와야합니다.
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])
약간의 추가 데이터를 저장해도 괜찮다면 최소값을 저장하는 것이 간단해야합니다. 푸시 및 팝은 새 요소 또는 제거 된 요소가 최소 인 경우 값을 업데이트 할 수 있으며 최소값을 반환하는 것은 변수 값을 가져 오는 것만 큼 간단합니다.
이것은 get_min ()이 데이터를 변경하지 않는다고 가정합니다. pop_min () (즉, 최소 요소 제거)과 같은 것을 원한다면 실제 요소와 그 앞에있는 요소 (있는 경우)에 대한 포인터를 저장하고 그에 따라 push_rear () 및 pop_front ()로 업데이트 할 수 있습니다. 게다가.
댓글 후 수정 :
분명히 이것은 해당 작업에 대한 최소 변경 사항이있는 경우 O (n) 푸시 및 팝으로 이어지며 요구 사항을 엄격하게 충족하지 않습니다.
코드를 포함한이 질문에 대한 해결책은 여기에서 찾을 수 있습니다. http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32
실제로 LinkedList를 사용하여 대기열을 유지할 수 있습니다.
LinkedList의 각 요소는 유형이됩니다.
class LinkedListElement
{
LinkedListElement next;
int currentMin;
}
두 개의 포인터를 가질 수 있습니다. 하나는 시작을 가리키고 다른 하나는 끝을 가리 킵니다.
큐의 시작 부분에 요소를 추가하는 경우. 시작 포인터와 삽입 할 노드를 확인합니다. 삽입 할 노드 currentmin이 start currentmin보다 작 으면 삽입 할 currentmin 노드가 최소값입니다. 그렇지 않으면 start currentmin으로 currentmin을 업데이트합니다.
enque에 대해서도 동일하게 반복하십시오.
#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;
}
이 솔루션에는 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
자바 구현
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);
}
}
}
우리는 푸시와 팝이 일정한 시간 작업이라는 것을 알고 있습니다 [정확히 O (1)].
그러나 get_min () [즉, 큐에서 현재 최소 수를 찾는 것]을 생각할 때 일반적으로 가장 먼저 떠오르는 것은 최소 요소에 대한 요청이있을 때마다 전체 큐를 검색하는 것입니다. 그러나 이것은 문제의 주요 목표 인 일정한 시간 작동을 제공하지 않습니다.
이것은 일반적으로 인터뷰에서 매우 자주 요청되므로 트릭을 알아야합니다.
이를 위해 최소 요소를 추적하는 두 개의 큐를 더 사용해야하며 최소 요소가 O (1) 시간에 얻어 지도록 큐에서 푸시 및 팝 작업을 수행 할 때이 두 큐를 계속 수정해야합니다. .
다음은 위에서 언급 한 접근 방식을 기반으로 한 자체 설명적인 sudo 코드입니다.
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;
}
JavaScript 구현
( 아이디어에 대한 adamax의 솔루션에 대한 크레딧 ; 저는 이에 대한 구현을 느슨하게 기반으로했습니다. 아래로 이동하여 완전히 주석 처리 된 코드를 보거나 아래의 일반적인 단계를 읽어보십시오. 이것은 O (1) 상수 시간에서 최대 값 을 찾는 것이 아니라 최소 값은 그랬다고)를 변경합니다 :
일반적인 아이디어는 생성시 두 개의 스택을 만드는 것입니다
MaxQueue(Stack코드에 포함되지 않은 기본 데이터 구조 로 연결된 목록을 사용했습니다 .하지만StackO (1) 삽입 / 삭제로 구현되는 한 모든 작업 이 수행됩니다). 하나는 주로pop(dqStack)에서, 다른 하나는 주로push(eqStack)로 이동합니다.
삽입 : O (1) 최악의 경우
의
enqueue경우MaxQueue가 비어 있으면 튜플 의 현재 최대 값과 함께pushtodqStack값 (에서 유일한 값이므로 동일한 값 )이됩니다. 예 :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) 상각
들어
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최대 한 번 으로 이동하기 때문에dequeueO (1) 상각 된 시간 복잡도가 있다고 말할 수 있습니다 .
최대 값 찾기 : O (1) 최악의 경우
그런 다음 언제든지
getMaxO (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];
}
}'programing' 카테고리의 다른 글
| package.json에 node_modules 경로 지정 (0) | 2020.10.22 |
|---|---|
| 오류 : Microsoft Visual C ++ 10.0이 필요합니다 (vcvarsall.bat를 찾을 수 없음). (0) | 2020.10.21 |
| 부트 스트랩 요소 100 % 너비 (0) | 2020.10.21 |
| grunt (minimatch / glob) 폴더 제외 (0) | 2020.10.21 |
| 부동 소수점 숫자에 부호있는 0이있는 이유는 무엇입니까? (0) | 2020.10.21 |