练习6.5-8—最小堆k路合并
《算法导论》第六章主要内容是关于堆和优先级队列，书中给出了一个练习题，非常有有意思，今天好好研究练习一下。题目如下：请给出一个时间为O(nlgk)、用来将k个已排序链表合并为一个排序链表的算法。此处n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）。
看到题目第个想到的是归并排序过程中的归并操作子过程，从头开始两两比较，找出最小的，然后接着往后比较，常用的是2路归并。而题目给的是k个已排好序的链表(k>=2)。如果没有提示，我半天不知道如何去实现，幸好提示说用最小堆来做k路合并，于是我想到可以这样做：创建一个大小为k的数组，将k个链表中的第一个元素依次存放到数组中，然后将数组调整为最小堆，这样保证数组的第一个元素是最小的，假设为min，将min从最小堆取出并存放到最终结果的链表中，此时将min所在链表的下一个元素到插入的最小堆中，继续上面的操作，直到堆中没有元素为止。举个例子如下图所示（只给出不部分操作）：
现在采用C++语言，借助STL实现此过程，链表采用list，最小堆中存放的是list的迭代器，表示list中元素的位置。完整程序如下：
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <cstdlib>
using namespace std;
template<class T> class MinHeap
{
public:
MinHeap();
MinHeap(const size_t size);
~MinHeap();
T get_min() const;
void delete_min();
void insert_element(const T& e);
void adjust_min_heap(const size_t i);
size_t get_heap_size() const;
int compare(const T& t1,const T& t2);
private:
T *heap;
size_t heap_size;
};
template<class T>
MinHeap<T>::MinHeap():heap(NULL),heap_size(0){}
template<class T>
MinHeap<T>::MinHeap(const size_t size)
{
if(!heap)
delete [] heap;
heap = new T[size+1];
heap_size = 0;
}
template<class T>
MinHeap<T>::~MinHeap()
{
if(!heap)
delete [] heap;
heap_size = 0;
}
template<class T>
T MinHeap<T>::get_min() const
{
if(heap_size > 0)
return heap[1];
else
return T();
}
template<class T>
void MinHeap<T>::delete_min()
{
if(heap_size > 0)
{
heap[1] = heap[heap_size];
heap_size = heap_size - 1;
adjust_min_heap(1);
}
else
{
cout<<"Error: the min heap is empty"<<endl;
}
}
template<class T>
void MinHeap<T>::insert_element(const T& e)
{
size_t i,parent;
T temp;
heap_size = heap_size + 1;
heap[heap_size] = e;
i = heap_size;
parent = i/2;
while(i>1 && compare(heap[parent],heap[i]) > 0)
{
temp = heap[parent];
heap[parent] = heap[i];
heap[i] = temp;
i = parent;
parent = i/2;
}
}
template<class T>
void MinHeap<T>::adjust_min_heap(const size_t i)
{
size_t left,right,least;
T temp;
left = i*2;
right = i*2+1;
if(left <= heap_size && compare(heap[left],heap[i]) < 0)
least = left;
else
least = i;
if(right <= heap_size && compare(heap[right],heap[least]) < 0)
least = right;
if(least != i)
{
temp = heap[least];
heap[least] = heap[i];
heap[i] = temp;
adjust_min_heap(least);
}
}
template<class T>
size_t MinHeap<T>::get_heap_size() const
{
return heap_size;
}
template<class T>
int MinHeap<T>::compare(const T& t1,const T& t2)
{
return (*t1-*t2);
}
const static int k = 3;
int main()
{
list<int> lists[k];
list<int>::iterator iters[k];
list<int> retlist;
list<int>::iterator retiter;
list<int>::iterator iter;
MinHeap<list<int>::iterator> minheap(k);
//first list <12,24,52>
lists[0].push_back(12);
lists[0].push_back(24);
lists[0].push_back(52);
cout<<"First list: ";
for(iter=lists[0].begin();iter != lists[0].end();++iter)
cout<<*iter<<"->";
cout<<"NULL"<<endl;
//second list <9,32>
lists[1].push_back(9);
lists[1].push_back(32);
cout<<"Second list: ";
for(iter=lists[1].begin();iter != lists[1].end();++iter)
cout<<*iter<<"->";
cout<<"NULL"<<endl;
//third list <34,42,78>
lists[2].push_back(34);
lists[2].push_back(42);
lists[2].push_back(78);
cout<<"Third list: ";
for(iter=lists[2].begin();iter != lists[2].end();++iter)
cout<<*iter<<"->";
cout<<"NULL"<<endl;
iters[0] = lists[0].begin();
iters[1] = lists[1].begin();
iters[2] = lists[2].begin();
minheap.insert_element(iters[0]);
minheap.insert_element(iters[1]);
minheap.insert_element(iters[2]);
while(minheap.get_heap_size())
{
iter = minheap.get_min() ;
retlist.push_back(*iter);
minheap.delete_min();
++iter;
if(iter != lists[0].end() && iter != lists[1].end()
&&iter != lists[2].end())
minheap.insert_element(iter);
}
cout<<"Merge the there list is: "<<endl;
for(retiter = retlist.begin();retiter!= retlist.end();retiter++)
cout<<*retiter<<"->";
cout<<"NULL"<<endl;
exit(0);
}
效果如下：
作者：费德
已有 3 条评论
添加新评论
最新文章
全部分类
[url=https://szybkamasa.pl/]tabletki na nabranie masy[/url]
[url=https://bliskilekarz.pl/rehabilitacja-medyczna]rehabilitacja-medyczna[/url]
Informacje Sosnowiec [url=http://informacjesosnowiec.pl/kategoria/Lokalne-uslugi]http://informacjesosnowiec.pl/kategoria/Lokalne-uslugi[/url]