Priority Queues

Priority Queue

• 우선순위를 가진 요소에 언제든 접근할 수 있는 구조

PQType

PQType(int max)

items : 구조체 HeapType 이름.

elements : HeapType 멤버 중 데이터 저장하는 배열.

template <class ItemType>
PQType<ItemType>::PQType(int max){
	length = 0;
    items.elements = new ItemType[max];
    maxItems = max;
}

~PQType()

배열을 삭제해줘야한다!

template <class ItemType>
PQType<ItemType>::~PQType(){
	delete []items.elements;
}

 

void MakeEmpty()

template <class ItemType>
void PQType<ItemType>::MakeEmpty(){
	length = 0;
}

 

bool IsEmpty()

template <class ItemType>
bool PQType<ItemType>::IsEmpty(){
	return (length == 0);
}

 

bool IsFull()

template <class ItemType>
bool PQType<ItemType>::IsFull(){
	return (length == maxItems);
}

 

Enqueue(ItemType newItem)

힙 마지막에 item 추가

길이 +1

ReheapUp으로 힙 구조 맞춰주기

template <class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem){
	length++;
    items.elements[length] = newItem;
    items.ReheapUp(0,length-1);
}

 

Dequeue(ItemType& item)

비어있는 큐인지 확인 후 item에 가장 큰 원소 저장( root = items.elements[0])

root 자리에 트리의 가장 마지막 원소 저장

길이 -1

ReheapDown으로 힙 구조 맞춰주기

template <class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item){
	item = items.elements[0];
    items.elements[0] = items.elements[length-1];
    length--;
    items.ReheapDown(0,length-1);
}

 

시간복잡도