[Data Structure] Priority Queue

 

 

Complete Binaray Tree 

every level, all nodes are filled ordering left to right except possibly last node

 

When to use?

-> Implements Prirority Queue!

 

* Full Binrary Tree : every node has two children

 

 

ADT of Prirority Queue implements using MAX Heap

array -> parent index : i / 2

left child index : i * 2

right child index : i * 2 + 1

 

maxSize: Capacity

size: The number of current elements which heap has

 

[Operations]

• shiftUp
• shiftDown
• changePrirority
• getParent
• getLeftChild
• getRightChild
• insert
• getMax // these include shiftDown since this remove root node
• removeElement

💡 removeElement

 (1) when impelment prioirity queue using array

    a) find element and make prirority of that node as ∞ and shift up

    b) getMax

 (2) when impelment prioirity queue using linked list

     a) find element using binrary search and mark it rootNode 

     b) getMax

 

Implement (C++)

PriorityQueue.h

PrirorityQueue.cpp

main.cpp

 

 

 

Tip in C++ STL

큐 초기화시 다음과 같이 배열의 시작주소와 끝주소를 명시하여

buildHeap과 priority queue 생성을 같이하는 방식이 있다.

💡 operator 연산자를 오버라이딩 하지 않는 경우 기본적으로 최대 힙으로 생성된다.

 

다음 예제는 무게가 적은 순으로 최소 힙으로 구현된 우선순위 큐를 초기화 하고있다.

    struct Node {
        unsigned int nodeNumber;
        // max weight is 1000
        unsigned int weight = 1000;
    };

    struct CompareWeight {
        bool operator()(const Node& previousNode, const Node& nextNode) const {
            return previousNode.weight > nextNode.weight;
        }
    };
    
    std::priority_queue<Node, std::vector<Node>, CompareWeight> priorityQueue(nodes, nodes + V);

※ 또, vector는 capacity 를 넘어가면 복사가 일어나므로 원소 갯수가 많을 경우 위와 같은 방법이 더 효과적이다.

 

(다만 change Priority 연산을 지원하지 않는 것이 흠이다.)

---

Reference

Efficient way to initialize a priority queue - GeeksforGeeks