#include <stdio.h>
#include <stdlib.h>
/**
* 经常使用 heap 实现 优先级队列
*/
#define MAX_SIZE 100
#define True 1
#define False 0
typedef short Boolean;
typedef struct node* pNode;
struct node{
int data;
};
pNode heap[MAX_SIZE+1]; /// index of first element is 1
int size;
Boolean isFull();
Boolean isEmpty();
void insert(pNode);
pNode delete(); ///// delete the biggest node
void print();
pNode getMax();
#include "deap.h"
void print()
{
if(isEmpty()){
return;
}
int i = 1;
while(i <= size){
printf("%d ", heap[i++]->data);
}
printf("\n");
}
Boolean isFull()
{
if(size == MAX_SIZE+1) return True;
return False;
}
Boolean isEmpty()
{
if(size == 0) {
printf("Empty deap\n");
return True;
}
return False;
}
// while 循环从最大堆的 新叶子结点 开始,
// 沿着到根结点的路径,直到根结点
// 使其父结点 i/2 的值 不小于 要插入的值
void insert(pNode elem)
{
if(isFull(size)){
printf("sizeo space\n");
return;
}
int i = ++size;
while(i!=1 && elem->data > heap[i/2]->data){ /// 把父结点移动到其子结点位置
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = elem;
}
/// 删除根元素,然后把最后一个元素设为根元素,
/// 接着进行调整,使之复合最大堆/最小堆
pNode delete(){
pNode res = 0;
if(isEmpty()){
return 0;
}
res = heap[1]; /// 得到最大元素
pNode last = heap[size--]; /// 得到最后一个元素
//heap[1] = last;
int parent = 1; //// 从新的 根元素 开始
int child = 2; /// 新的根元素的 孩子
while(child <= size){
if(child < size && heap[child]->data < heap[child+1]->data){ ////// 比较兄弟结点,取较大者的下标
child++;
}
if(heap[child]->data > last->data){ //// 如果 较大的子结点 大于 新的 根结点
heap[parent] = heap[child]; //// 那么把 该子结点 移动到 父结点位置
parent = child; /// 当前子结点设为 起点 重新开始移动
child *= 2;
}else{
break;
}
}
heap[parent] = last;
return res;
}
pNode getMax(){
if(!isEmpty()){
return heap[1];
}
return 0;
}
分享到:
相关推荐
二叉堆(最小堆)+二项堆+斐波那契堆 根基算法导论C++实现
由两部分组成,my_map.cpp用OpenCV实现读取地图等图像处理操作,main.cpp实现A*算法。二叉堆为类,格子为结构体。生成结果后进行优化,使原本只能走8个方向的结果优化为任意角度和方向,也就是真正的全局最短路径。
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 直接执行该文件会执行文件中的测试样例 使用时在头部如此声明 from binaryheap import BinaryHeap bh = BinaryHeap(heap_size) # heap_...
c++实现的二叉堆,很好的编程规范,可以学到模板、inline函数、引用的实际应用。代码写的很简洁
PHP对于二叉堆的操作,以及个人的理解,可进行插入、删除操作等
二叉堆的C++实现,包含二叉堆的构造,插入,删除,销毁等操作
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重
使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。
基于二叉堆的AStar算法演示程序,简单高效。使用VS2010+MFC演示,算法与平台无关,可以任意使用。
4.binaryHeap 二叉堆 支持排序,父子之间只有一种大小关系。孩子大于父,或者小于父。 二叉堆不支持合并。 实现了各种增删查改算法。
易语言二叉堆源码,二叉堆,加入二叉,减出二叉,寻找数值
本人做的一个二叉堆的课件,附带STL中的priority_queue
二叉堆、并查集和树状数组 刘汝佳 绝对经典巧妙的讲解和解答
二叉堆的概念及其应用,里面包含果子合并、堆排序、鱼塘钓鱼、最小函数值、Sequence等重要题型的详细解析
C# 二叉堆 压出最小值比较快
本源代码借助标准C++ STL中的vector,list和heap等已封装的数据结构,优化了A星算法搜索地图、检索开始列表过程,减小了程序的时间和空间花费。经检验,检索20000*20000的随机障碍物地图时,程序在规划路径部分的平均...
使用C++实现了A星算法,使用二叉堆优化。仅供新手学习。
使用c++实现最大堆。提供常见操作,如插入、删除、堆化数组、堆排序、上下调整、向下调整。
二叉堆的相关代码.zip二叉堆的学习与思考