Priority Queues, Heaps

# Implementation with a Sorted Sequence

# Sorted Sequence


//define Node. Node has value,key, and prev,next node pointer.
template <typename T>
class Node {
    public:
    	T value;
        int key;
        Node *prev, *next;
        
        Node(T val, int k)
        	:value(val), key(k), prev(nullptr), next(nullptr) [}
};


//define PriorityQueue. It has insert, findMinValue, findMinKey, removeMinNode.
template <typename T>
class MinPriorityQueue {
    private:
    	DoublyLinkedList<T> list;
        
    public:
    	void insertItem(T value, int key);
        T minElement();
        int minKey();
        T removeMinElement();
};


//return head value.
T minElement() {
    if(list.isEmpty()){
   	    throw std::runtime_error("Priority Queue is empty.");
    }
    return list.head->value;
}

//return head key.
int minKey() {
    if(list.isEmpty()){
   	    throw std::runtime_error("Priority Queue is empty.");
    }
    return list.head->key;
}

//return head value and remove head node.
T removeMinelement() {
    if(list.isEmpty()){
   	    throw std::runtime_error("Priority Queue is empty.");
    }
    T minValue = list.head->value;
    list.remove(list.head);
    return minValue;
}

//insert Item
void insertItem(T value, int key) {
    Node<T> *newNode = new Node<T>(value, key);
    if(list.isEmpty()){
   	    list.head = list.tail = newNode;
    }else {
        Node<T> *current = list.head;
        while(current && current->key <= key){
        	current = current->next;
        }
        if(current) list.insertBefore(current, value, key);
        else list.insertAfter(list.tail, value, key);
    }
}

## Selection Sort ( Unstored Seq)

Phase1) Insert : 그대로 삽입 : O(1)

Phase2) removeMin : minValue를 Select해서 삽입하며 sort : O(n)

=> Thus total time complexity of the algorithm is O(n^2)

## Insertion Sort (Sorted Seq)

Phase1) Insert : minValue를 바로 Insert하며 삽입 : O(n)

Phase2) removeMin : Sort된 리스트를 그대로 복사 : O(1)

=> Thus total time complexity of the algorithm is O(n^2). Always 끝까지 탐색해야함.

## Heap

Phase1) Insert : O(logn)

Phase2) removeMin : O(logn)

=> Thus total time complexity of the algorithm is O(nlogn). 중간에 큰 값을 만나면 중지.

# Heaps

- 부모 노드가 자식 노드보다 커야 함

- height = log(n+1)

## Bottom-up Heap Construction

- It takes O(n) time complexity.