스택 만 사용하여 효율적인 우선 순위 큐를 구현합니다

Question

는 스택 데이터 구조를 사용하여 효율적인 우선 순위 대기열 (힙으로서 효율적으로) 만 구현할 수 있습니까?

힙을 사용하여 구현 된 우선 순위 대기열의 일반적인 효율은 다음과 같습니다.

• get min - $ o (1) $
• 추출기 - $ o (\ log n) $
• add - $ o (\ log n) $

스택 만 사용하여 동일한 복잡성으로 무언가를 수행 할 수 있습니까?

i * (노드의 우선 순위를 사용하여 노드 우선 순위를 지정하는 데 우선 순위 큐를 사용하는)를 구현하고 있지만 Minecraft는 무작위 액세스를 허용하지 않으며 구현할 수있는 가장 효율적인 동적 구조가 스택입니다.

Answer 1

불행히도, 가능하지 않습니다.스택에서 항목을 추출한 순서는 해당 항목의 값에 관계없이 푸시 된 순서에만 의존합니다.우선 순위 대기열은 항목의 값에 따라 다르게되는 순서로 제거 할 항목이 필요합니다.

Answer 2

(바이너리) 힙 데이터 구조를 사용하여 우선 순위 대기열의 완벽한 표현을 수행 할 수 있습니다. 스택 및 대기열을 구현할 수 있습니다 ...

우선 순위 대기열에서는 스택과 같은 필로 원칙이 아닌 기본 설정이 아니라

Cormen et al., 알고리즘 소개, 3 판 소개,

을 찾을 수 있습니다.

힙을 사용하는 우선 순위 대기열 구현은 힙, max_heap 또는 min_heap의 속성과 관련이 있으므로 build_heap () first, max_heapify (), express_key ()와 같은 힙에 사용되는 절차를 사용하여 min_heap을 사용하여 min_heap을 사용하여 구현할 수 있습니다., 삽입 및 삭제.

(바이너리) 힙 자체는 거의 완전한 바이너리 검색 트리로 표시 될 수있는 배열 개체입니다 ...

스택 구현의 경우 (psudo 코드가 있음)

class Stack 
    Inner class Element 
       int priority   // priority of the element.
       Key element    // the element it self

    MAX_PRIORITY_QUEUE<Element> queue;
    next_priority = 0;

    void push(Key x) // value of the pushed element
        q.push(Element(next_priority++, x))

    Key pop() 
        // as popping some element the next push must take its place
        next_priority-- 
        return queue.pop().element

.

우선 순위 대기열 (힙)을 사용하여 대기열을 구현하지만 우선 순위는 다른 후에 하나씩 감소합니다.