C++实现优先队列——最小堆，d路堆及配对堆
发布时间
阅读量：
阅读量
实现优先队列，在本处所述之优先队列是基于Huffman树实现的（具体参考上一篇文章）。因此，在比较过程中使用的都是huffman树中的node频率，请读者注意。
最小堆（二叉）：
template <typename T>
class MinHeap
{
public:
MinHeap(int cap );
~MinHeap();
public:
bool insert(pTree val);
bool remove(pTree data);
void print();
int size;
T getTop();
bool createMinHeap(pTree a[], int length);
private:
int capacity;
T * heap;
private:
void filterUp(int index);
void filterDown(int begin, int end);
};
template <typename T>
MinHeap<T>::MinHeap(int cap )
:capacity(cap), size(0), heap(nullptr)
{
heap = new pTree[capacity];
};
template<typename T>
MinHeap<T>::~MinHeap()
{
delete[]heap;
};
template <typename T>
void MinHeap<T>::print()
{
for (int i = 0; i < size; i++)
cout << heap[i]->freq << " ";
};
template <typename T>
T MinHeap<T>::getTop()//返回最小值
{
if (size != 0)
return heap[0];
};
template <typename T>
bool MinHeap<T>::insert(pTree val)//插入函数
{
if (size == capacity)
return false;
heap[size] = val;
filterUp(size);
size++;
return true;
};
template <typename T>
void MinHeap<T>::filterUp(int index)//由上至下进行调整
{
pTree value = heap[index];
while (index > 0)
{
int indexParent = (index-1) / 2;
if (value->freq >= heap[indexParent]->freq)
break;
else
{
heap[index] = heap[indexParent];
index = indexParent;
}
}
heap[index] = value;
};
template<typename T>
bool MinHeap<T>::createMinHeap(pTree a[], int length)
{
if (length > capacity)
return false;
for (int i = 0; i < length; i++)
{
insert(a[i]);
}
return true;
};
template<typename T>
bool MinHeap<T>::remove(pTree data)//删除元素
{
if (size == 0)
return false;
int index;
for (index = 0; index < size; index++)
{
if (heap[index]== data)
break;
}
if (index == size)
return false;
heap[index] = heap[size - 1];
size--;
filterDown(index, size);
return true;
};
template<typename T>
void MinHeap<T>::filterDown(int current, int end)//由下至上进行调整
{
int child = current * 2 + 1;
pTree value = heap[current];
while (child <= end)
{
if (child < end && heap[child]->freq > heap[child + 1]->freq)
child++;
if (value->freq<heap[child]->freq)
break;
else
{
heap[current] = heap[child];
current = child;
child = child * 2 + 1;
}
}
heap[current] = value;
};
代码解释配对堆：
class PairNode
{
public:
pTree element;
PairNode *leftChild;
PairNode *nextSibling;
PairNode *prev;
PairNode(pTree element)
{
this->element = element;
leftChild = NULL;
nextSibling = NULL;
prev = NULL;
}
};
class PairingHeap
{
private:
PairNode *root;
void reclaimMemory(PairNode *t);
void compareAndLink(PairNode * &first, PairNode *second);
PairNode *combineSiblings(PairNode *firstSibling);
PairNode *clone(PairNode *t);
public:
PairingHeap();
PairingHeap(PairingHeap &rhs);
~PairingHeap();
bool isEmpty();
bool isFull();
pTree &findMin();
PairNode *Insert(pTree &x);
void deleteMin();
void deleteMin(pTree &minItem);
void makeEmpty();
void decreaseKey(PairNode *p, pTree &newVal );
PairingHeap &operator=(PairingHeap &rhs);
};
PairingHeap::PairingHeap()
{
root = NULL;
}
PairingHeap::PairingHeap(PairingHeap & rhs)
{
root = NULL;
*this = rhs;
}
/* * Destroy the leftist heap.
*/
PairingHeap::~PairingHeap()
{
makeEmpty();
}
/* * Insert item x into the priority queue, maintaining heap order.
* Return a pointer to the node containing the new item.
*/
PairNode *PairingHeap::Insert(pTree &x)
{
PairNode *newNode = new PairNode(x);
if (root == NULL)
root = newNode;
else
compareAndLink(root, newNode);
return newNode;
}
/* * Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
pTree &PairingHeap::findMin()
{
return root->element;
}
/* * Remove the smallest item from the priority queue.
* Throws Underflow if empty.
*/
void PairingHeap::deleteMin()
{
PairNode *oldRoot = root;
if (root->leftChild == NULL)
root = NULL;
else
root = combineSiblings(root->leftChild);
delete oldRoot;
}
/* * Remove the smallest item from the priority queue.
* Pass back the smallest item, or throw Underflow if empty.
*/
void PairingHeap::deleteMin(pTree &minItem)
{
if (isEmpty())
{
cout<<"The Heap is Empty"<<endl;
return;
}
minItem = findMin();
deleteMin();
cout<<"Minimum Element: "<<minItem<<" deleted"<<endl;
}
/* * Test if the priority queue is logically empty.
* Returns true if empty, false otherwise.
*/
bool PairingHeap::isEmpty()
{
return root == NULL;
}
/* * Test if the priority queue is logically full.
* Returns false in this implementation.
*/
bool PairingHeap::isFull()
{
return false;
}
/* * Make the priority queue logically empty.
*/
void PairingHeap::makeEmpty()
{
reclaimMemory(root);
root = NULL;
}
/* * Deep copy.
*/
PairingHeap &PairingHeap::operator=(PairingHeap & rhs)
{
if (this != &rhs)
{
makeEmpty( );
root = clone(rhs.root);
}
return *this;
}
/* * Internal method to make the tree empty.
*/
void PairingHeap::reclaimMemory(PairNode * t)
{
if (t != NULL)
{
reclaimMemory(t->leftChild);
reclaimMemory(t->nextSibling);
delete t;
}
}
/* * Change the value of the item stored in the pairing heap.
* Does nothing if newVal is larger than currently stored value.
* p points to a node returned by insert.
* newVal is the new value, which must be smaller
* than the currently stored value.
*/
void PairingHeap::decreaseKey(PairNode *p, pTree &newVal)
{
if (p->element->freq < newVal->freq)
return;
p->element = newVal;
if (p != root)
{
if (p->nextSibling != NULL)
p->nextSibling->prev = p->prev;
if (p->prev->leftChild == p)
p->prev->leftChild = p->nextSibling;
else
p->prev->nextSibling = p->nextSibling;
p->nextSibling = NULL;
compareAndLink(root, p);
}
}
/* * Internal method that is the basic operation to maintain order.
* Links first and second together to satisfy heap order.
* first is root of tree 1, which may not be NULL.
* first->nextSibling MUST be NULL on entry.
* second is root of tree 2, which may be NULL.
* first becomes the result of the tree merge.
*/
void PairingHeap::compareAndLink(PairNode * &first, PairNode *second)
{
if (second == NULL)
return;
if (second->element->freq < first->element->freq)
{
second->prev = first->prev;
first->prev = second;
first->nextSibling = second->leftChild;
if (first->nextSibling != NULL)
first->nextSibling->prev = first;
second->leftChild = first;
first = second;
}
else
{
second->prev = first;
first->nextSibling = second->nextSibling;
if (first->nextSibling != NULL)
first->nextSibling->prev = first;
second->nextSibling = first->leftChild;
if (second->nextSibling != NULL)
second->nextSibling->prev = second;
first->leftChild = second;
}
}
/* * Internal method that implements two-pass merging.
* firstSibling the root of the conglomerate;
* assumed not NULL.
*/
PairNode *PairingHeap::combineSiblings(PairNode *firstSibling)
{
if (firstSibling->nextSibling == NULL)
return firstSibling;
static vector<PairNode *> treeArray(5);
int numSiblings = 0;
for (; firstSibling != NULL; numSiblings++)
{
if (numSiblings == treeArray.size())
treeArray.resize(numSiblings * 2);
treeArray[numSiblings] = firstSibling;
firstSibling->prev->nextSibling = NULL;
firstSibling = firstSibling->nextSibling;
}
if (numSiblings == treeArray.size())
treeArray.resize(numSiblings + 1);
treeArray[numSiblings] = NULL;
int i = 0;
for (; i + 1 < numSiblings; i += 2)
compareAndLink(treeArray[i], treeArray[i + 1]);
int j = i - 2;
if (j == numSiblings - 3)
compareAndLink (treeArray[j], treeArray[j + 2]);
for (; j >= 2; j -= 2)
compareAndLink(treeArray[j - 2], treeArray[j] );
return treeArray[0];
}
/* * Internal method to clone subtree.
*/
PairNode *PairingHeap::clone(PairNode * t)
{
if (t == NULL)
return NULL;
else
{
PairNode *p = new PairNode(t->element);
if ((p->leftChild = clone( t->leftChild)) != NULL)
p->leftChild->prev = p;
if ((p->nextSibling = clone( t->nextSibling)) != NULL)
p->nextSibling->prev = p;
return p;
}
}
代码解释d路堆：
class DaryHeap
{
private:
int d;
int currentSize;
int size;
pTree *array;
public:
/* * Constructor
*/
DaryHeap(int capacity, int numKids)
{
currentSize = 1;
d = numKids;
size = capacity + 1+1;
array=new pTree[capacity + 1+1];
}
/* * Constructor , filling up heap with a given array
*/
/* * Function to check if heap is empty
*/
bool isEmpty()
{
return currentSize == 1;
}
/* * Check if heap is full
*/
bool isFull()
{
return currentSize == size;
}
/* * Clear heap
*/
void makeEmpty( )
{
currentSize = 1;
}
/* * Function to get index parent of i
*/
int parent(int i)
{
return (i - 1) / d+1;
}
/* * Function to get index of k th child of i
*/
int kthChild(int i, int k)
{
return d * i + k+1;
}
/* * Function to inset element
*/
void Insert(pTree x)
{
if (isFull())
{
cout<<"Array Out of Bounds"<<endl;
return;
}
int hole = currentSize;
currentSize++;
array[hole] = x;
percolateUp(hole);
}
/* * Function to find least element
*/
pTree findMin()
{
if (isEmpty())
{
cout<<"Array Underflow"<<endl;
return 0;
}
return array[1];
}
/* * Function to delete element at an index
*/
pTree Delete(int hole)
{
if (isEmpty())
{
cout<<"Array Underflow"<<endl;
return 0;
}
pTree keyItem = array[hole];
array[hole] = array[currentSize - 1];
currentSize--;
percolateDown( hole );
return keyItem;
}
/* * Function to build heap
*/
void buildHeap()
{
for (int i = currentSize - 1 ; i >=1; i--)
percolateDown(i);
}
/* * Function percolateDown
*/
void percolateDown(int hole)
{
int child;
pTree tmp = array[hole];
for ( ; kthChild(hole, 1) < currentSize; hole = child)
{
child = smallestChild( hole );
if (array[child]->freq < tmp->freq)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
/* * Function to get smallest child from all valid indices
*/
int smallestChild(int hole)
{
int bestChildYet = kthChild(hole, 1);
int k = 2;
int candidateChild = kthChild(hole, k);
while ((k <= d) && (candidateChild < currentSize))
{
if (array[candidateChild]->freq < array[bestChildYet]->freq)
bestChildYet = candidateChild;
k++;
candidateChild = kthChild(hole, k);
}
return bestChildYet;
}
/* * Function percolateUp
*/
void percolateUp(int hole)
{
pTree tmp = array[hole];
for (; hole > 1 && tmp->freq < array[parent(hole)]->freq; hole = parent(hole))
array[hole] = array[ parent(hole) ];
array[hole] = tmp;
}
};
代码解释在其中，最慢的速度属于配对堆。其核心在于通过一系列合并操作来重构整个数据结构。
采用三种优先队列对一百万大量数据进行十次构建Huffman树所需的时间如下所述。总体而言，在相同的数据规模下深度优先堆与最小堆所花时间基本相当。这是因为两者均基于数组结构实现。
此次体会最大的收获是，在性能上静态数组确实优于动态数据结构。然而在存储空间方面，则会带来一定的额外开销。其运行效率值得肯定。
全部评论 (0)
还没有任何评论哟~