• 小顶堆是堆顶元素最小（控制堆中元素个数，比堆顶元素的元素才能入堆，可以用来确定第k的数） class MinHeap{ private int capacity; private int count; private int[] elements; public MinHeap(int ...
小顶堆
小顶堆是堆顶元素最小（控制堆中元素个数，比堆顶元素大的元素才能入堆，可以用来确定第k大的数）
class MinHeap{
private int capacity;
private int count;
private int[] elements;

public MinHeap(int capacity) {
this.capacity = capacity;
elements = new int[capacity];
}

public void insert(int num) {
if (count >= capacity) return;
elements[count] = num; // 新加入的元素放堆底部
// 从底部向上调整
int pos = count;
while (pos > 0 && elements[pos] < elements[(pos - 1) / 2]) {
swap(pos, (pos - 1) / 2);
pos = (pos - 1) / 2;
}
count++;
}

public void poll() {
if (count == 0) return;

//将堆底元素放入堆顶，相当于移除了堆顶元素
elements[0] = elements[--count];
// 从上向下进行调整
int pos = 0;
while (true) {
// 将当前节点值与左右节点的较小值进行交换
int targetPos = pos;
if (2 * pos + 1 < count && elements[targetPos] > elements[2 * pos + 1]) targetPos = 2 * pos + 1;
if (2 * pos + 2 < count && elements[targetPos] > elements[2 * pos + 2]) targetPos = 2 * pos + 2;
if (targetPos == pos) break; // 说明已经调整完了
swap(pos, targetPos);
pos = targetPos;
}
}

public int peek() {
return elements[0];
}

public int size() {
return this.count;
}
private void swap(int a, int b) {
int tmp = elements[a];
elements[a] = elements[b];
elements[b] = tmp;
}
}

大顶堆 参考小顶堆实现
class MaxHeap {
private int capacaty;
private int count;
private int[] elements;

public MaxHeap(int capacity) {
this.capacaty = capacity;
elements = new int[capacity];
}

public void insert(int num) {
if (count >= capacaty) return;
elements[count] = num;

int pos = count;
while (pos > 0 && elements[pos] > elements[(pos - 1) / 2]) {
swap(pos, (pos - 1) / 2);
pos = (pos - 1) / 2;
}

count++;
}

public Integer poll() {
if (count <= 0) return null;
int res = elements[0];

int pos = 0;
elements[pos] = elements[--count];

while (true) {
int targetPos = pos;
if (2 * pos + 1 < count && elements[targetPos] < elements[2 * pos + 1]) targetPos = 2 * pos + 1;
if (2 * pos + 2 < count && elements[targetPos] < elements[2 * pos + 2]) targetPos = 2 * pos + 2;
if (targetPos == pos) break;
swap(pos, targetPos);
pos = targetPos;
}

return res;
}

private void swap(int a, int b) {
int tmp = elements[a];
elements[a] = elements[b];
elements[b] = tmp;
}

public int size() {return this.count;}
public int peek() {return elements[0];}
}

展开全文
• L2-012. 关于堆的判断 时间限制 400 ms 内存限制 65536 kB ...将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种： “x is
 L2-012. 关于堆的判断

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
“x is the root”：x是根结点； “x and y are siblings”：x和y是兄弟结点； “x is the parent of y”：x是y的父结点； “x is a child of y”：x是y的一个子结点。
输入格式：
每组测试第1行包含2个正整数N（<= 1000）和M（<= 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式：
对输入的每个命题，如果其为真，则在一行中输出“T”，否则输出“F”。
输入样例：
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

输出样例：
F
T
F
T#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int l,n,m,a[1010];
void A(int index)
{
int t=a[index];
int j=index;
while(j>1&&a[j/2]>t)   //a[j/2]<t及为大顶堆
{
a[j]=a[j/2];
j/=2;
}
a[j]=t;
}
void Q(int y)
{
a[l++]=y;
A(l-1);
}
int main ()
{
int x,ky;
l=1;
string str;
map<int,int> vis;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&x);
Q(x);
}
for(int i=1;i<l;i++)
{
vis[a[i]]=i;
//cout<<a[i]<<" ";
}
for(int i=0;i<m;i++)
{
cin>>ky;
int xb=vis[ky];
cin>>str;
if(str[0]=='a')
{
cin>>ky;
getline(cin,str);
int xb1=vis[ky];
if(xb/2==xb1/2)
cout<<"T"<<endl;
else
cout<<"F"<<endl;
}
else
{
cin>>str;
cin>>str;
if(str[0]=='r')
{
if(xb==1)
cout<<"T"<<endl;
else
cout<<"F"<<endl;
}
else if(str[0]=='p')
{
cin>>str;
cin>>ky;
int xb1=vis[ky];
if(xb1/2==xb)
cout<<"T"<<endl;
else
cout<<"F"<<endl;
}
else
{
cin>>str;
cin>>ky;
int xb1=vis[ky];
if(xb1==xb/2)
cout<<"T"<<endl;
else
cout<<"F"<<endl;
}
}
}
system("pause");
return 0;
}


展开全文
• 一、大顶堆小顶堆的原理 1、大顶堆 根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。 2、...
一、大顶堆和小顶堆的原理
1、大顶堆
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。
2、小顶堆
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者，称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值。
3、大顶推和小顶堆的实现
public class MaxHeap {
public static void main(String[] args) {
//原始数组内容
int i,size,data[]={0,5,6,10,8,3,2,19,9,11};

size=data.length;

System.out.print("原始数组：");

for(i=1;i<size;i++)
System.out.print("["+data[i]+"] ");

System.out.println("");
//建立堆积树
MaxHeap.heap(data,size);
}
public static void heap(int data[] ,int size)
{
int i,j,tmp;
//建立堆积树节点
for(i=(size/2);i>0;i--)
System.out.print("\n堆积内容：");
//原始堆积树内容
for(i=1;i<size;i++)
System.out.print("["+data[i]+"] ");
}

public static void ad_heap(int data[],int i,int size){
int j,tmp,post;
j=2*i;
tmp=data[i];
post=0;
while(j<=size && post==0)
{
if(j<size)
{
//小顶堆的比较
//if(data[j]>data[j+1])
//找出两个子节点最大值
if(data[j]<data[j+1])
j++;
}
//小顶堆的比较
//if(tmp<=data[j])
//若树根较大，结束比较过程
if(tmp>=data[j])    {
post=1;
} else {
//若树根较小，则继续比较，这里将最大子节点赋值给父节点
data[j/2]=data[j];
j=2*j;
}
}
//指定树根为父节点
data[j/2]=tmp;
}
}
二、小顶堆的应用
1、求最大的k个数
1、求10亿个数中的最大的前10个数，时时构建只有10个元素的小顶堆，如果比堆顶小，则不处理；如果比堆顶大，则替换堆顶，然后依次下沉到适当的位置。 详细讲解请看公众号:码农有道2、选择最大的K个数
public class findTopK {
//用PriorityQueue默认是自然顺序排序，要选择最大的k个数，构造小顶堆，每次取数组中剩余数与堆顶的元素进行比较，如果新数比堆顶元素大，则删除堆顶元素，并添加这个新数到堆中。
//找出前k个最大数，采用小顶堆实现
public static int[] findKMax(int[] nums, int k) {
//队列默认自然顺序排列，小顶堆，不必重写compare
PriorityQueue<Integer> pq = new PriorityQueue<>(k);

for (int num : nums) {
if (pq.size() < k) {
pq.offer(num);
//如果堆顶元素 < 新数，则删除堆顶，加入新数入堆
} else if (pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}

int[] result = new int[k];
for (int i = 0; i < k&&!pq.isEmpty(); i++) {
result[i] = pq.poll();
}
return result;
}

public static void main(String[] args) {
int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
System.out.println(Arrays.toString(findKMax( arr,5)));
}
}
2、数组中的第K个最大元素
 // 小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int val : nums) {
// 维护堆的大小为 K
if (pq.size() > k) {
//弹出最顶端的数,并删除
pq.poll();
}
}
//取最顶端的数
return pq.peek();
}
三、大顶堆的应用

PriorityQueue通过传入自定义的compara函数可以实现大顶堆

1、要选择最小的K个数使用大顶堆，每次取数组中剩余数与堆顶的元素进行比较，如果新数比堆顶元素小，则删除堆顶元素，并添加这个新数到堆中。
public static int[] findKMin(int[] nums,int k ){
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});

for (int num:nums){
if (pq.size() <k){
pq.offer(num);
//如果堆顶元素 > 新数，则删除堆顶，加入新数入堆
}else if(pq.peek() > num){
pq.poll();
pq.offer(num);

}
}
int[] result = new int[k];
for (int i = 0;i<k&&!pq.isEmpty();i++){
result[i] = pq.poll();
}
return result;
}

public static void main(String[] args) {
int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
System.out.println(Arrays.toString(findKMin( arr,5)));
}

2、数组中的第K个最小元素
   public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});

for (int val : nums) {
// 维护堆的大小为 K
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
展开全文
• 学生，代码资源，希望大家能有用。
• ## C++大顶堆和小顶堆

千次阅读 2020-11-24 09:04:59
C++大顶堆小顶堆原理大顶堆小顶堆大顶堆小顶堆对比图大顶堆小顶堆的实现代码 原理   堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构（或者也有可能是满二叉树） 大顶堆   根结点（亦称为堆顶...


C++大顶堆和小顶堆
原理大顶堆小顶堆大顶堆和小顶堆对比图大顶堆和小顶堆的实现代码
vector和push_heap、pop_heap实现堆建堆调整堆
priority_queue实现堆简述模板参数成员函数大顶堆和小顶堆

原理
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构（或者也有可能是满二叉树）
大顶堆
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。
小顶堆
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者，称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值。
大顶堆和小顶堆对比图

大顶堆和小顶堆的实现代码
heap.h
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;

template<class T>
struct Less
{
bool operator()(const T& left, const T& right) const
{
return left < right;
}
};

template<class T>
struct Greater
{
bool operator()(const T& left, const T& right) const
{
return left > right;
}
};

template<class T, class Compare = Less<T>>
class Heap
{
public:
Heap()//无参的构造函数（系统不会给无参构造函数），开始堆是空的不需要做什么事
{}
Heap(T* a, size_t n)
{
_a.reserve(n);//开空间
for (size_t i = 0; i < n; ++i)
{
_a.push_back(a[i]);

}
//建堆,找最后一个非叶子节点
for (int i = (_a.size() - 2) / 2; i >= 0; --i)//不用size_t，因为i在这可能等于0，用size_t会死循环
{
}
}
//向下调整
{
Compare com;
int parent = root;
size_t child = parent * 2 + 1;//默认为左孩子
while (child < _a.size())
{
//选出小孩子
//if (child+1 > _a.size() && _a[child + 1]< _a[child])
if (child + 1 < _a.size() && com(_a[child + 1], _a[child]))
{
++child;
}

//if (_a[child] < _a[parent])
if (com(_a[child], _a[parent]))
{
swap(_a[child], _a[parent]);//交换值
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//向上调整
{
Compare com;
int parent = (child - 1) / 2;
while (parent >= 0)
{
//if (_a[child] < _a[parent])
if (com(_a[child], _a[parent]))
{
swap(_a[parent], _a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}

}
//最后插入
void Push(const T&x)
{
_a.push_back(x);
}
//删除最大数
void Pop()
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);
_a.pop_back();

}
//取顶元素
T& Top()
{
assert(!_a.empty());
return _a[0];
}
size_t Size()
{
return _a.size();
}

bool Empty()
{
return _a.empty();
}

private:
vector<T> _a;

};

main.cpp
#include <iostream>
#include "heap.h"
using namespace std;

int main()
{
int a[] = { 10,11,13,12,16,18,15,17,14,19 };
// Heap<int,Greater<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最大堆
// Heap<int,Less<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最小堆
Heap<int> hp1(a, sizeof(a) / sizeof(a[0])); // 缺省，最小堆
hp1.Push(15);
system("pause");
return 0;
}

vector和push_heap、pop_heap实现堆
建堆
vector<int> nums = {9, 6, 2, 4, 7, 0, 1, 8, 3, 5};

如何使用nums构建最大堆
make_heap(nums.begin(), nums.end());
//或
make_heap(nums.begin(), nums.end(), less<int>());

如何使用nums构建最小堆
make_heap(nums.begin(), nums.end(), greater<int>());

调整堆
当使用上述的make_heap()建完堆后，如果vector使用push_back()插入数据或pop_back()删除数据后，会破坏最大堆/最小堆的性质，所以需要调整堆，常用push_heap()和pop_heap()两个方法。 1、push_heap()用法是，vector先push_back()，后push_heap()
nums.push_back(10);
push_heap(nums.begin(), nums.end(), less<int>());

2、pop_heap()用法是，先pop_heap()，vector后pop_back()
pop_heap(nums.begin(), nums.end(), less<int>());
nums.pop_back();

为什么pop_heap()的用法要反过来呢？ 要从我们的目的来考虑，使用pop_heap()的绝大部分目的是要把堆顶元素pop出堆中，因为它最大或最小。如果先用vector的pop_back()，它删除的不是堆顶元素（nums[0]），而是vector的最后一个元素。可见这不是我们想要的结果：对于最大堆，最后一个元素既不是最大，也不一定是最小；对于最小堆，最后一个元素既不是最小，也不一定是最大。pop出来没有意义。 观察pop_heap()对堆做了什么？ pop_heap()把堆顶元素放到了最后一位，然后对它前面的数字重建了堆。这样一来只要再使用pop_back()把最后一位元素删除，就得到了新的堆。
priority_queue实现堆
priority_queue 对于这个模板类priority_queue，它是STL所提供的一个非常有效的容器。 作为队列的一个延伸，优先队列包含在头文件 中。
简述
优先队列时一种比较重要的数据结构，它是有二项队列编写而成的，可以以O(log n) 的效率查找一个队列中的最大值或者最小值，其中是最大值还是最小值是根据创建的优先队列的性质来决定的。
模板参数
优先队列有三个参数，其声明形式为：
priority_queue< type, container, function >

这三个参数，后面两个可以省略，第一个不可以。其中： **type：**数据类型； **container：**实现优先队列的底层容器； **function：**元素之间的比较方式； 对于container，要求必须是数组形式实现的容器，例如vector、deque，而不能使list。 在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。
成员函数
假设type类型为int，则：
bool empty() const 返回值为true，说明队列为空；int size() const 返回优先队列中元素的数量；void pop() 删除队列顶部的元素，也即根节点；int top() 返回队列中的顶部元素，但不删除该元素；void push(int arg) 将元素arg插入到队列之中。
大顶堆和小顶堆
#include <functional>

//构造一个空的优先队列（此优先队列默认为大顶堆）
priority_queue<int> big_heap;
//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;

//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;

展开全文
• 下面编就为大家分享一篇Java 堆排序实例(大顶堆小顶堆)，具有很好的参考价值，希望对大家有所帮助。一起跟随编过来看看吧
• ## 小顶堆和大顶堆

千次阅读 2017-11-05 19:26:26
这几天学习了顶(ding)堆(dang)和顶(ding)堆(dang)  模板题  小顶堆-木柴切割 这是一道小顶堆的模板题，和合并果子一模一样差不多。  题目描述  FarmerJohn想修理牧场栅栏的某些段。为此，他需要N(1 ...
• PriorityQueue（优先队列） 是一个基于优先级堆的无界优先级队列，底层实现是一棵完全二叉树 不允许使用 null 元素 不允许插入不可比较的对象，会导致 ClassCastException。...实现小顶堆 PriorityQueue
• 堆是一种非线性结构，(本篇随笔主要分析堆的数组实现)可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组按照堆的特点可以把堆分为大顶堆小顶堆大顶堆：...
• 大顶堆小顶堆的理论是相同的，实现上就只有符号的变化。 堆的含义 堆是类似与完全二叉树的结构（注意可能不是满二叉树）， 堆的结构是要使得每个根节点的元素大于（与）子节点元素，左右节点是没有要求的。 ...
• 1、大顶堆：头部为堆中最大的值 2、小顶堆：头部为队中最小的值 3、PriorityQueue：一个具有优先级的队列，该优先级使得队列始终按照自然顺序进行排序，队列的头部为最小值。 构造小顶堆： PriorityQueue small=new...
• 大顶堆 每个结点的值都大于或等于其左右孩子结点的值 小顶堆 每个结点的值都小于或等于其左右孩子结点的值 对比图 实现代码 public class HeapNode{ private int size;//堆大小 private int[] heap;//保存堆数组 ...
• //创建小顶堆大顶堆 Queue<>() queue1 = new PriorityQueue<>(); //创建小顶堆（优先队列），堆顶元素是最小元素 Queue<>() queue2 = new PriorityQueue<>(); //创建大顶堆，堆顶元素是...
• ## 堆排序（浅谈大顶堆与小顶堆）

万次阅读 多人点赞 2019-09-14 15:20:11
堆是一种非线性结构，（本篇随笔主要分析堆的数组实现）可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组，按照堆的特点可以把堆分为大顶堆小顶堆。...
• 大顶堆小顶堆，也叫优先队列，是一种基于数组+平衡二叉树的数据结构。 主要用于排序，增减操作的速度较快（O(logn)） 适合带有优先级的排序场景，比如处理订单的时候，VIP用户的优先级更高，当前队列有人排队可以...
• 首先明确堆是一个完全二叉树，小顶堆指根结点的值小于或等于左右子节点的值，大顶堆指根结点的值都大于或等于左右子节点的值 关于大小顶堆的建立更详细的介绍 #include<iostream> #include<cstdio> #...
• 下面以大顶堆讲解一些堆的相关知识，并给出小顶堆的代码。 首先，既然是顺序存储，且又是完全二叉树的结构，其节点如何存储呢？此处使用二叉树的层次遍历方式存储节点值，本文使用的节点...
• 大顶堆代码、小顶堆代码 实际应用及实例代码 小顶堆删除图解代码、插入代码 小顶堆插入图解 时间复杂度分析 1、百度-》概念：堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种...
• 按照堆的特点可以把堆分为大顶堆小顶堆 大顶堆：每个结点的值都大于或等于其左右孩子结点的值 小顶堆：每个结点的值都小于或等于其左右孩子结点的值 使用堆的原因？ 如果仅仅是需要得到一个有序的序列，使用排序就...
• 目录堆的定义堆的相关操作插入元素删除顶点元素 堆的定义 是一个完全二叉数 ...每个节点大于其子树节点的堆叫做大顶堆 每个节点小于其子树节点的堆叫做小顶堆 堆的相关操作 插入元素 删除顶点元素 ...
• ​ 堆是一种数据结构，实质是利用完全二叉树结构来维护的一维数组，按照堆的特点可以把堆分为大顶堆小顶堆大顶堆：每个结点的值都大于或等于其左右孩子结点的值； 小顶堆：每个结点的值都小于或等于其左右孩子...
• ## 堆排序，大顶堆，小顶堆

万次阅读 多人点赞 2014-02-10 15:50:27
代码如下，有详细的注视 ... /** * ... * 步骤1：构建大顶堆(或小顶堆) * 步骤2：将 堆顶 元素 与 未排序 的最后一个叶子，进行交换 * 步骤3：并对半堆进行修正(不考虑已有序的叶子) * 步骤
• 目录：1、前期参考2、大顶堆原理3、小顶堆原理4、大顶堆小顶堆对比图5、大顶堆代码6、执行结果————————————————————————————-1、前期参考使用一维数组存储二叉树 ...
• i--)//遍历这个数的所有非叶结点 ，挨个把所有的子树，变成子大顶堆 { HeapAjust(i, data, data.Length); //经过上面的for循环，是把二叉树变成了大顶堆 } for (int i = data.Length; i > 1; i--) {//把 编号1 和...

...