优秀营销网站设计,石家庄网络推广建站,郑州开发app公司哪家好,溧水区城乡建设局网站堆的定义 • 堆是一个完全二叉树 –所有叶子在同一层或者两个连续层 –最后一层的结点占据尽量左的位置 • 堆性质 –为空, 或者最小元素在根上 –两棵子树也是堆 存储方式 • 最小堆的元素保存在heap[1..hs]内 – 根在heap[1] –K的左儿子是2k,…堆的定义 • 堆是一个完全二叉树 –所有叶子在同一层或者两个连续层 –最后一层的结点占据尽量左的位置 • 堆性质 –为空, 或者最小元素在根上 –两棵子树也是堆 存储方式 • 最小堆的元素保存在heap[1..hs]内 – 根在heap[1] –K的左儿子是2k, K的右儿子是2k1, –K的父亲是[k/2] 删除最小值元素 • 三步法 – 直接删除根 – 用最后一个元素代替根上元素 – 向下调整 • 首先选取当前结点p的较小儿子如果比p大, 调整停止否则交换p和儿子, 继续调整 插入元素和向上调整 • 插入元素是先添加到末尾, 再向上调整 • 向上调整: 比较当前结点p和父亲, 如果父亲比p小停止; 否则交换父亲和p, 继续调整 堆的建立堆的构造 1、自底向上堆构造算法 在初始化一棵包含几个节点的完全二叉树时按给定的顺序来效置键然后按照下面的方法对树进行“堆化”如下图从最后的父母节点开始到根为止该算法检查这些节点的键是否满足父母优势要求。如果该节点不满足该算法把节点的键k和它子女的最大键进行交换然后再检查在新位置上k是不是满足父母优势要求。这个过程一直继续到对k的父母优势要求满足为止对于以当前父母节点为根的子树在完成了它“堆化”以后该算法对于该节点的直接前趋进行同样的操作。在对树的根完成了这种操作以后该算法就停止了。 2、自顶向下堆构造算法 通过把新的键连续插入预先构造好的堆来构造一个新堆如何把一个新的键k插入到堆中呢首先把一个包含键k的新节点附加在当前堆的最后一个叶子后面然后按照下面的方法把k筛选到它的适当位置拿k和它父母的键作比较如果后者大于等于k算法停止否则交换这两个键并把k和它的新父母做比较。这种交换一直持续到k不大于它的最后一个父母或者是达到了树的根为止如下图。在这个算法中我们也可以把一个空节点向上筛选直到达到合适的位置才把k的值赋予它。 显然这个插入操作所需的键值比较次数不可能超过堆的高度。因为包含几个节点的堆的高度大约是log2n所以插入的时间效率属于ologn。 删除堆中某个元素不一定是堆顶元素 1、以堆中最后一个元素取代被删除元素留下的空位此举确保堆首先是一个完全二叉树。 2、堆调整堆化。 时间复杂度分析 • 向上调整/向下调整 – 每层是常数级别, 共logn层, 因此为O(logn) • 插入/删除 – 只调用一次向上或向下调整, 因此都是O(logn) • 建堆 – 高度为h的结点有n/2h1个,总时间为O(n*logn) 【堆这种数据结构适合解决何种类型的问题】 ........ D$#():M|{_#!SAQ$GBD^KFG(*$#$BK}{?:X~^ 【堆排序实践】 输入n个整数 n 10^5按从大到小排序后输出。 操作步骤 1) 建立堆。直接在待排序数据A[]上建立最大堆 2) 重复调整堆。取出堆首元素根元素交换至堆尾部堆容量减1继续调整。
优秀范例代码展示构架清晰、代码简洁、高效
输入输出格式
输入格式 二行第一行一个整数值n n 10^5 第二行n个整数每个整数均小于2^31每个整数间有一个空格间隔。
输出格式 一行排好序从大到小的顺序的n个数据每个数据间用一个空格间隔。
输入输出样例
输入样例#1
4 4 5 2 897
输出样例#1
897 5 4 2
提示信息
如果仅仅为了AC那么排序吧
sort也有一定概率堆排
#includebits/stdc.h
#define sp sort
using namespace std;
int n,a[100010];
int cmp(int x,int y)
{return xy;
}
int main()
{cinn;for(int i1;in;i){cina[i];}sp(a1,an1,cmp);for(int i1;in;i){couta[i] ;}return 0;
}
