Created
June 5, 2013 11:40
-
-
Save kingsamchen/5713295 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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"\n"); | |
} | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment