우선순위 대기열, 코드 참조 범례
7225 단어 우선 순위
1. 버전 정보
2. 사전 처리 정보
3. 라이브러리 함수 참조
4. 일반 프로그래밍
5. 매크로 정의
6. 복제 구조 함수
7. 내수 함수
8. 변수 명명 규범
9. 코드의 시간 공간 효율
10. 오류 복구 능력
11. 사양명세 주석 및 들여쓰기
코드 예:
/***************************************
** Project:PriorityQueue
** File:priqueue.h
** Edition:v1.0.0 Demo
** Coder:KingsamChen [MDSA Group]
** Last Modify:2011-9-1
****************************************/
#if _MSC_VER > 1000
#pragma once
#endif
#ifndef _PRIQUEUE_05232021_A052_400f_ADD6_8FA21FDCBF7E
#define _PRIQUEUE_05232021_A052_400f_ADD6_8FA21FDCBF7E
#include <cassert>
#include <cstdio>
#define PARENT(x) (((x) - 1) >> 1)
#define LEFTCHILD(x) (((x) << 1) + 1)
#define RIGHTCHILD(x) (((x) + 1) << 1)
template<typename T>
class CPriQueue
{
public:
typedef int pos;
public:
CPriQueue();
CPriQueue(const CPriQueue& q);
~CPriQueue();
public:
CPriQueue& operator =(const CPriQueue& q);
void BuildHeap(const T ary[], int count);
void Insert(const T& ele);
T ExtractMin();
inline T Min() const;
inline int GetCount() const;
inline bool IsEmpty() const;
inline bool IsFull() const;
pos Find(const T& ele) const;
void DecreaseKey(pos p, unsigned int det);
void IncreaseKey(pos p, unsigned int det);
void Delete(pos p);
// diagnostic interface
#if _DEBUG
void DgPrint();
#endif
private:
void PercolateUp(int i, const T& ele);
void PercolateDown(int i, const T& ele);
private:
enum{INI_CAPCITY = 50, NOT_FOUND = -1};
T* m_pHeap;
int m_capcity;
int m_count;
};
template<typename T>
CPriQueue<T>::CPriQueue() : m_count(0)
{
m_pHeap = new T[INI_CAPCITY];
assert(m_pHeap != NULL);
m_capcity = INI_CAPCITY;
}
template<typename T>
CPriQueue<T>::CPriQueue(const CPriQueue& q) : m_capcity(q.m_capcity),
m_count(q.m_count)
{
m_pHeap = new T[m_capcity];
assert(m_pHeap != NULL);
// the element may have internal handle pointing to the extra data outside
// assume that the object already overloaded operator =
for (int i = 0; i < m_count; ++i)
{
m_pHeap[i] = q.m_pHeap[i];
}
}
template<typename T>
CPriQueue<T>::~CPriQueue()
{
if (m_pHeap != NULL)
{
delete [] m_pHeap;
m_pHeap = NULL;
m_capcity = 0;
m_count = 0;
}
}
template<typename T>
CPriQueue<T>& CPriQueue<T>::operator =(const CPriQueue& q)
{
if (m_capcity < q.m_count)
{
// need to expand
assert(false);
}
m_count = q.m_count
for (int i = 0; i < m_count; ++i)
{
m_pHeap[i] = q.m_pHeap[i];
}
return *this;
}
template<typename T>
void CPriQueue<T>::Insert(const T& ele)
{
if (IsFull())
{
// Logs error or expands capcity of the heap
assert(false);
}
// new element may violate heap property
PercolateUp(m_count, ele);
++m_count;
}
/*
Description:
Adjusts the specific element which may violate the heap property
upward.
Parameters:
i[in] - the position in the heap of the specific element.
ele[in] - a copy of the element. It's used to make the function more
efficient. Do not have this parameter refered to the element directly.
It may possible change the value of the ele while adjusting.
Return Value:
none
*/
template<typename T>
void CPriQueue<T>::PercolateUp(int i, const T& ele)
{
for (int p = PARENT(i); ele < m_pHeap[p]; p = PARENT(p))
{
// reaches the root
if (0 == i)
{
break;
}
m_pHeap[i] = m_pHeap[p];
i = p;
}
m_pHeap[i] = ele;
}
template<typename T>
T CPriQueue<T>::ExtractMin()
{
assert(!IsEmpty());
T ret(m_pHeap[0]);
// new root violates the heap property
PercolateDown(0, m_pHeap[--m_count]);
return ret;
}
/*
Description:
It is Similar to the function PercolateUp but downward.
Parameters:
i[in] - the position in the heap of the specific element.
ele[in] - the same as in PercolateUp
Return Value:
none
*/
template<typename T>
void CPriQueue<T>::PercolateDown(int i, const T& ele)
{
for (; LEFTCHILD(i) < m_count;)
{
// the node may have only left child
int iL = LEFTCHILD(i);
int iR = RIGHTCHILD(i);
int iMin = iR < m_count ? (m_pHeap[iL] < m_pHeap[iR] ? iL : iR) : iL;
if (m_pHeap[iMin] < ele)
{
m_pHeap[i] = m_pHeap[iMin];
i = iMin;
}
else
{
break;
}
}
m_pHeap[i] = ele;
}
template<typename T>
inline T CPriQueue<T>::Min() const
{
assert(!IsEmpty());
return m_pHeap[0];
}
template<typename T>
inline int CPriQueue<T>::GetCount() const
{
return m_count;
}
template<typename T>
inline bool CPriQueue<T>::IsEmpty() const
{
return 0 == m_count ? true : false;
}
template<typename T>
inline bool CPriQueue<T>::IsFull() const
{
return m_capcity == m_count ? true : false;
}
/*
Description:
Returns the position of the specific element to be found. The function
takes O(N) time
Parameters:
ele[in] - the element we search for
Return Value:
The function returns NOT_FOUND if the specific element is not found
otherwise the return value indicates the position of the element
*/
template<typename T>
typename CPriQueue<T>::pos CPriQueue<T>::Find(const T& ele) const
{
pos index = NOT_FOUND;
for (int i = 0; i < m_count; ++i)
{
if (m_pHeap[i] == ele)
{
index = i;
break;
}
}
return index;
}
template<typename T>
void CPriQueue<T>::DecreaseKey(pos p, unsigned int det)
{
assert(p >= 0);
m_pHeap[p] -= det;
T newEle(m_pHeap[p]);
// adjusts the order property
PercolateUp(p, newEle);
}
template<typename T>
void CPriQueue<T>::IncreaseKey(pos p, unsigned int det)
{
assert(p >= 0);
m_pHeap[p] += det;
T newEle(m_pHeap[p]);
PercolateDown(p, newEle);
}
template<typename T>
void CPriQueue<T>::Delete(pos p)
{
assert(p >= 0);
int det = m_pHeap[p] - m_pHeap[0] + 1;
DecreaseKey(p, det);
ExtractMin();
}
/*
Description:
Builds up the heap from an array
Parameters:
ary[in] - the array contains elements
count[in] - indicates the counts of the elements in array
Return Value:
none
*/
template<typename T>
void CPriQueue<T>::BuildHeap(const T ary[], int count)
{
assert(m_capcity >= count);
for (int i = 0; i < count; ++i)
{
m_pHeap[i] = ary[i];
}
m_count = count;
for (int i = PARENT(count - 1); i >= 0; --i)
{
T eleMov(m_pHeap[i]);
PercolateDown(i, eleMov);
}
}
#if _DEBUG
template<typename T>
void CPriQueue<T>::DgPrint()
{
for (int i = 0; i < m_count; ++i)
{
wprintf_s(L"%d\t", m_pHeap[i]);
}
wprintf_s(L"
");
}
#endif
#endif
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
MongoDB 실전 시리즈 4: mongodb 던전 세트 배포약술: 복제본 집합(Replica Sets)은 주/종 복제 메커니즘을 기반으로 하는 복제 기능이지만 자동 고장 전이와 복구 기능을 추가했다.하나의 집단은 최대 7개의 서버를 지원할 수 있고 임의의 노드가 주 노드가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.