主要完成维护一个min-heap or max-heap,如果push的个数超过heap的大小,则进行替换,依赖于compare函数。
其中min-heap需要定义 return a < b; max-heap: return a > b
在空间不够的情况下,min-heap保留最大的k个元素,max-heap相反。
code:
template<typename Type>
class LessThan
{
public:
bool operator()(const Type& first, const Type& second)
{
return first < second;
}
};
#ifndef _HEAP_H_
#define _HEAP_H_
#include "utility.h"
#include <string.h>
#define DEFAULT_BUFF_NUM 1000
namespace utility
{
//Compare, return a>b, 0,1,2,3 return a<b, 3,2,1,0
template<typename Type, typename Compare = LessThan<Type> >
class Heap
{
public:
Heap(int capacity = 0);
~Heap();
int push(const Type& type);
Type pop();
Type top();
int size();
int capacity();
bool empty();
private:
int ShiftUp();
int ShiftDown();
int Parent(int i);
int Left(int i);
int Right(int i);
private:
int mSize;
int mCapacity;
Type* mpHeap;
Compare mCompare;
};
template<typename Type, typename Compare>
int Heap<Type, Compare>::Parent(int i)
{
return int((i + 1) / 2) - 1;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::Left(int i)
{
return 2 * (i + 1) - 1;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::Right(int i)
{
return 2 * (i + 1);
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::ShiftUp()
{
// sucks
int i = mSize - 1;
while (i > 0)
{
int parent = Parent(i);
// need to modify
if (!mCompare(mpHeap[parent], mpHeap[i]))
{
Swap(mpHeap[parent], mpHeap[i]);
}
else
{
break;
}
i = parent;
}
return 0;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::ShiftDown()
{
// sucks
int i = 0;
while (i < mSize)
{
int left = Left(i);
int right = Right(i);
int modify = -1;
if ((right < mSize))
{
if (mCompare(mpHeap[left], mpHeap[right]))
{
modify = left;
}
else
{
modify = right;
}
}
else if (left < mSize)
{
modify = left;
}
if (modify < 0)
{
break;
}
if (!mCompare(mpHeap[i], mpHeap[modify]))
{
Swap(mpHeap[i], mpHeap[modify]);
}
else
{
break;
}
i = modify;
}
return 0;
}
template<typename Type, typename Compare>
Heap<Type, Compare>::Heap(int capactiy):
mSize(0),
mCapacity(capactiy),
mpHeap(NULL)
{
if (mCapacity <= 0)
{
mCapacity = DEFAULT_BUFF_NUM;
}
mpHeap = new Type[mCapacity];
memset(mpHeap, 0, mCapacity * sizeof(Type));
}
template<typename Type, typename Compare>
Heap<Type, Compare>::~Heap()
{
delete[] mpHeap;
mpHeap = NULL;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::push(const Type& type)
{
if (mSize < mCapacity)
{
mpHeap[mSize] = type;
++mSize;
ShiftUp();
}
else
{
// small element on the top
if (!mCompare(type, mpHeap[0]))
{
mpHeap[0] = type;
ShiftDown();
}
}
return 0;
}
template<typename Type, typename Compare>
Type Heap<Type, Compare>::top()
{
return mpHeap[0];
}
template<typename Type, typename Compare>
Type Heap<Type, Compare>::pop()
{
Type type = mpHeap[0];
if (mSize == 1)
{
--mSize;
return type;
}
mpHeap[0] = mpHeap[mSize - 1];
--mSize;
ShiftDown();
return type;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::size()
{
return mSize;
}
template<typename Type, typename Compare>
int Heap<Type, Compare>::capacity()
{
return mCapacity;
}
template<typename Type, typename Compare>
bool Heap<Type, Compare>::empty()
{
return mSize <= 0;
}
}
#endif
分享到:
相关推荐
min_MAX Heap!! Algorithm
make_minmax_heap)-时间(基准_heap_baseline) 计算弹出项目的时间时间(benchmark_pop_minmax_heap_min)-时间(benchmark_make_minmax_heap)或时间(benchmark_pop_minmax_heap_max)-时间(benchmark_make_min...
最小最大堆 提供 min-heap 和 max-heap 的 Java 实现,这是一种高效的数据结构,广泛用于解决从项目列表中获取前 k 个元素的问题
一最小最大堆(min max heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小 。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所 为一最小最大堆; min ...
最小/最大堆数据结构和堆排序算法的完整javascript实现。 最小堆 最大堆 目录 。叶子() 。尺寸() 。克隆() 。已验证() 。使固定() 。种类() 。清除() Heap.heapify(清单) Heap....
min-max-heap:双端优先级队列min-max-heap类似于二进制堆,但是它允许提取最小有效值和最大值efficien min-max-heap:双端优先级队列A min- max-heap类似于二进制堆,但是它允许有效地提取最小值和最大值。...
average_code [计算平均值]可用于用户抢红包等 1: red_envelope_code [二倍均值法] 可用于用户抢红包等 ... 1: max_heap_test 大顶推 2: min_heap_test 小顶堆 linked_list [链表] 1: cycle_list 循环链表 2: dou
Javascript 中的二进制堆实现 二叉堆是满足堆排序特性的完全二叉树。 排序可以是以下两种类型之一: min-heap属性:每个节点的值都大于或等于其父节点的值,最小值元素位于根节点。 max-heap属性:每个节点的值都...
void heap_sort(sqlist *l); //堆排序 *****重要 void max_heapadjust(sqlist *l, int s, int m); //建堆 的过程 (从顺序表的s下标到m下标 建堆) void min_heapadjust(sqlist *l, int s, int m); //小顶堆 void ...
include_recipe 'minecraft'service 'minecraft' do action :enableendservice 'minecraft' do action :startend属性 { "minecraft": { "user": "minecraft", "max_heap": 2048, "min_heap": 1024 }}贡献分
logical_and, logical_or, logical_not 7.6 证同(identity)、选择(select)、投射(project) 423 identity, select1st, select2nd, project1st, project2nd 第8章 配接器(adapter) 425 8.1 配接器之概观与...
/opt/nexus-data \ -p 8081:8081 -p 5000:5000 \ --ulimit nofile=65536 \ --name nexus-repository-oss \ 04n0/nexusrepmanoss:3.30-alpine 如果需要覆盖JVM内存的默认配置,则可以将环境变量JVM_HEAP_MIN和/或JVM_...
logical_and, logical_or, logical_not 7.6 证同(identity)、选择(select)、投射(project) 423 identity, select1st, select2nd, project1st, project2nd 第8章 配接器(adapter) 425 8.1 配接器之概观与...
23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 局部排序复制partial_sort...
23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 局部排序复制partial_sort...
CS146 编程项目 II:构建一个实现最小-最大堆(整数)的程序。 您的 ADT 必须支持以下操作: buildMinMaxHeap(int array) 给定一个整数数组。 Int peekMin() Int peekMax() Int deleteMin() Int deleteMax() Insert...
23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 局部排序复制partial_sort...
算法和数据结构。 算法库,数据结构库,常见CS问题的各种解决方案。 安装 将此行作为托管依赖项添加到您的应用程序中: py-algorithms > =0, < 1 或使用pip软件包管理器在... - Min Heap - Max Heap - Priori
STL介绍 3 1、STL简介 3 2、算法 3 3、容器 3 4、迭代器 4 5、使用注意 4 一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 ...21. min / max / swap 39 22. numeric_limits 39
这是一本关于C++语言的百科全书,包括C和C++的命令、功能、编程和应用等方面的内容。全书分为五个部分:C++基础:C子集;C++的专有特征;标准函数库;标准C++类库;C++应用程序范例。详细描述和演示了定义C++语言的...