小顶堆大顶堆的概念大家应该都很熟悉了,如果不了解,可以搜索一下,网上很多介绍,而且很多源码实现,都很简单。
不过从网上看了一些堆的实现,都是用数组的。但是数组有一个缺陷,需要扩展时,就要复制原来的内存,申请新的空间。所以我在想能不能用链表,发现还真可以,就凑凑写了个代码。最后代码是写完了,发现其实链表没有必要,而且会占用更多的内存,尤其是对于那种int型变量,过多的指针真是浪费了大量内存。如果真要优化,可以针对数组做优化,链表不是出路。
反正代码写完了,拿出来晾一晾,呵呵。
代码在VS2008上编译测试通过,不过测试用例很简单。
#ifndef _HNWYLLMM_HEAP_H
#define _HNWYLLMM_HEAP_H
#include <map>
#include <iostream>
#include <cassert>
template<typename elem_t, typename cmp_func_t = std::less<elem_t> >
class cheap
{
public:
cheap() : m_root(NULL), m_last(NULL), m_count(0)
{
}
~cheap()
{
destroy() ;
}
int init()
{
m_last = m_root = NULL ;
m_count = 0 ;
return 0 ;
}
int destroy()
{
cheap_node *node = m_root ;
cheap_node *next = NULL ;
while (node)
{
next = node->_next ;
delete node ;
node = next ;
}
m_root = m_last = NULL ;
m_count ;
}
int size() const {return m_count ;}
int push(const elem_t &ele)
{
cheap_node *node = new cheap_node(ele) ;
if (!node)
return -1 ;
m_count++ ;
if (!m_last)
m_root = m_last = node ;
else
{
cheap_node *parent = m_last->_parent ;
if (!parent)
{
parent = m_last ;
m_last->_left = node ;
}
else if (parent->_left == m_last)
{
parent->_right = node ;
}
// parent's right child
else if (parent->_next)
{
parent = parent->_next ;
parent->_left = node ;
}
else
{
assert(0) ;
parent = m_root ;
for (parent = m_root ; parent->_left ; parent = parent->_left) ;
parent->_left = node ;
}
m_last->_next = node ;
node->_parent = parent ;
node->_prev = m_last ;
m_last = node ;
}
// 调整
cheap_node *next = m_last ;
cheap_node *parent = NULL ;
while ((parent = next->_parent) &&
m_cmp_func(next->_data, parent->_data)
)
{
elem_t tmp = next->_data ;
next->_data = parent->_data ;
parent->_data = tmp ;
}
return 0 ;
}
int pop(elem_t &ele)
{
if (!m_root)
return -1 ;
ele = m_root->_data ;
m_count-- ;
if (m_last == m_root)
{
delete m_last ;
m_root = m_last = NULL ;
return 0 ;
}
m_root->_data = m_last->_data ;
m_last->_data = NULL ;
if (m_last->_parent)
{
if (m_last->_parent->_left == m_last)
{
m_last->_parent->_left = NULL ;
}
else
{
m_last->_parent->_right = NULL ;
}
}
m_last = m_last->_prev ;
delete m_last->_next ;
m_last->_next = NULL ;
for (cheap_node *last = m_root, *node = NULL ; last ; last = node)
{
if (last->_right)
{
if (m_cmp_func(last->_left->_data, last->_right->_data))
{
node = last->_left ;
}
else
node = last->_right ;
}
else
node = last->_left ;
if (node)
{
if (m_cmp_func(node->_data, last->_data))
{
elem_t tmp = last->_data ;
last->_data = node->_data ;
node->_data = tmp ;
}
else
break ;
}
}
return 0 ;
}
friend cheap &operator <<(cheap &heap, const elem_t &ele)
{
heap.push(ele) ;
return heap ;
}
friend cheap &operator >>(cheap &heap, elem_t &ele)
{
heap.pop(ele) ;
return heap ;
}
void dump(std::ostream &os)
{
os << "dump: \n" ;
int i = 1, lvl = 0 ;
for (cheap_node *node = m_root ; node ; node = node->_next, i++)
{
os << node->_data << '\t' ;
if (i == (1 << lvl) )
{
os << std::endl ;
i = 0 ;
lvl++ ;
}
}
os << std::endl ;
}
private:
// 堆中的一个节点
// 包含了树的结构和链表的结构
// 还有一个数据
class cheap_node
{
public:
cheap_node * _parent ;
cheap_node * _left ;
cheap_node * _right ;
cheap_node * _next ;
cheap_node * _prev ;
elem_t _data ;
public:
cheap_node(const elem_t &ele) :
_parent(NULL),
_left(NULL),
_right(NULL),
_next(NULL),
_prev(NULL),
_data(ele)
{
}
~cheap_node()
{
}
};
private:
cheap_node * m_root ; // 第一个数据
cheap_node * m_last ; // 最后一个数据
int m_count ; // 统计个数
cmp_func_t m_cmp_func ; // 用来做比较的函数
};
#endif // _HNWYLLMM_HEAP_H
测试文件:
main.cpp
#include <iostream>
#include "heap_array.h"
using namespace std ;
int main(void)
{
cheap<int> heap ;
heap.push(6) ;
heap.dump(cout ) ;
// heap.push(5) ;
// heap << 100 << 5 << 9 << 11 ;
heap << 100 ; heap.dump(cout) ;
heap << 5 ; heap.dump(cout) ;
heap << 9 ; heap.dump(cout) ;
heap << 11 ; heap.dump(cout) ;
heap.dump(cout) ;
int num ;
while (0 == heap.pop(num))
{
cout << num << endl ;
heap.dump(cout) ;
}
return 0 ;
}