算法模版堆及其应用

1、堆及其应用堆的定义(二叉堆)n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：(1)kiK2i且kiK2i+1或(2)KiK2i且kiK2i+1(1in)。若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字堆的定义堆是一棵完全二叉树，它可分为大根堆和小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 堆的定义堆的定义： 1.二叉树的每一个节

2、点存储一个元素 2.二叉树的每一个非叶子所存储元素的优先级高于其儿子存储的元素的优先级。 堆的样例105670302515以上就是一个小根堆的样例堆的样例703010152556以上就是一个大根堆的样例堆的定义注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。 堆的样例16478953以上就是一个小根堆的样例堆支持的三种基本操作插入值 Insert 取最小值 Getmin删除最小值 Deletemin 堆的插入16478953例如：插入一个值为2。插入的过程中始终维护堆性质2堆的插入16478953例如：插入一个值为2。插入的过程中始终维护堆性质

3、2堆的插入16478953例如：插入一个值为2。插入的过程中始终维护堆性质2堆的删除16478953例如：删除堆顶元素，并且始终维护堆性质。2堆的删除6478953例如：删除堆顶元素，并且始终维护堆性质。2堆的删除6478953例如：删除堆顶元素，并且始终维护堆性质。2堆的删除6478953例如：删除堆顶元素，并且始终维护堆性质。2堆的删除6478953例如：删除堆顶元素，并且始终维护堆性质。2堆的数组实现由于堆有一些特殊的性质，所以我们可以用数组来实现堆。tot保存堆中元素的个数heapi (1=i1时，heapi的父亲存放在heapi div 2当中所以任何时刻当堆不为空的时候，堆的最小元

4、素始终存放在heap1的位置。 堆的插入操作代码实现Procedure Insert(x:longint);var s:integer;begin inc(tot); heaptot:=x; s:=tot; while (s1)and(heapsheaps div 2) do begin swap(heaps,heaps div 2); s:=s div 2; end;End;堆的删除操作代码实现Procedure Delete;var s:integer;begin heap1:=heaptot; dec(tot); s:=1; while (s*2=tot) do begin if (s*

5、2=tot) or (heaps*2heapj then begin swap(heaps,heapj); s:=j; end else exit; end;end;堆的各种操作的时间复杂度分析由于用数组实现的堆时刻是一棵近似满二叉树，因此插入和删除的操作时间复杂度仅跟这棵二叉树的高度有关系。每次操作的复杂度为O(logN)取最小值操作的时间复杂度为O(1).堆堆(heap)堆分为两种：小根堆和大根堆对于一个线性表s1.n 。小根堆：满足si=si*2且si=si*2且si=si*2+1堆 性质对于小根堆来说，s1是s1.n中的最小元素。对于大根堆来说，s1是s1.n中的最大元素。 应用范围查

6、找某个线性表中的最大值和最小值。时间复杂度为O(log2N)。堆堆的维护查找最小(大)值：find := s1插入一个元素key至表s中：totnode:=totnode+1;stotnode:=key;upchange(totnode);堆删除元素sw：sw:=stotnode;totnode:=totnode-1;downchange(w);两个操作upchange和downchange堆例题1（堆排序）将n个元素在O(nlogn)的时间复杂度内排序。hash和堆例题（促销活动） 促销活动遵守以下规则： 1一个消费者想参加促销活动的消费者，在账单下记下他自己所付的费用，他个人的详细情况，然

7、后将账单放入一个特殊的投票箱。 2当每天促销活动结束时，从投票箱中抽出两张账单： （1）第一张被抽出的账单是金额最大的账单 （2）然后被抽出的是金额最小的账单，对于付了金额最大账单的这位消费者，将得到一定数目的奖金，其奖金数等于他账单上的金额与选出的最小金额的差。 （3）为了避免一个消费者多次获奖，根据上面所抽出的两张账单都不返回到投票箱，但是剩下的账单还继续参加促销活动。hash和堆 超市的售出额是巨大的，这样可以假定，在每天结束，拿出数额最大账单和数额最小账之前，在投票箱内就已经至少存在了2张账单。 你的任务是去计算每天促销活动投进投票箱的账单数额的基本信息。在整个活动中开销总数。本题中约

8、定：1，整个活动持续了N天(N=5000)。2，第i天放入的帐单有ai张，ai=105。且sigma(a1.an)=106。3，每一天放入的帐单的面值均=106。hash和堆hnoi2005省选第二试最后一题试题分析：hnoi2005第一试最后一题试题分析：5、堆排序堆的定义：n个元素的序列k1,k2,.,kn当且仅当满足下列条件时，称之为堆。ki = k2iki = k2i+1或( i = 1, 2, . , n/2 )堆举例：96,83,27,38,11,09)12,36,24,85,47,30,53,919683381109271236854730245391 堆可以看成是一棵完全二叉树

9、结点的层次序列,且所有非叶结点的值均不大于(或不小于）左、右孩子结点的值堆排序的基本思想： 对一组待排序的关键码，首先把它们按堆的定义排列成一个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复进行，直到将全部关键码排好序为止。 根结点是堆中的最小元素。 实现堆要解决的问题 1、如何从一个无序序列建成一个堆？ 2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？ 例：图a是个堆，假设输出堆顶元素之后，以堆中最后一个元素代之，如图b。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。1236854730245391(

10、a)9136854730245312(b) 2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？ 首先以堆顶元素和其左、右子树根结点的值比较之，由于右子树根结点的值小于左子树根结点的值且小于根结点的值，则将24和91交换之； 由于91替代了24之后破坏了右子树的堆，则需要进行和上述相同的调整，直至叶子结点; 重复上述过程，将堆顶元素91和堆中最后一个元素30交换且调整，得到如图d所示新的堆。 称这个自堆顶至叶子的调整过程为“筛选”。 91368547302453(c)24368547913053(d)PROC sift（VAR r : listtype; k , m: integer ）;

11、假设r k+1 . . m 中各元素满足堆的性质，本算法调整r k 使整个序列r k . . m 中各元素满足堆的性质i : = k ; j : = 2 i ; x : = r k . key ; finished : = fakse ;t : = r k ; 暂存“根”记录r k WHILE (j=m) AND NOT finished DO IF (j rj+1 . Key) THEN j : = j +1; 若存在右子树，且右子树根的关键字小，则沿右分支“筛选” IF x 49,则交换之，交换后的序列如图b所示；49389776132749(a)654938497613652797(b) 同理，在第3个元素65被筛选之后序列的状态如图c所示。 由于第2个元素38不大于其左、右子树根的值，则筛选后的序列不变。 图e所示为筛选根元素49之后建成的堆。4938497665132797(c)4938497665132797(d)1338497665274997(e)堆排序算法：PROC heapsort（V