《ACM/ICPC 算法训练教程》读书笔记一之数据结构(堆)

  书籍简评:《ACM/ICPC 算法训练教程》这本书是余立功主编的,代码来自南京理工大学ACM集训队代码库,所以小编看过之后发现确实很实用,适合集训的时候刷题啊~~,当时是听了集训队final的意见买的,感觉还是不错滴。

  相对于其他ACM书籍来说,当然如书名所言,这是一本算法训练书,有着大量的算法实战题目和代码,尽管小编还是发现了些许错误= =,有部分注释的语序习惯也有点不太合我的胃口。实战题目较多是比较水的题,但也正因此才能帮助不少新手入门,个人认为还是一本不错的算法书,当然自学还是需要下不少功夫的。

  小编认为这本书主要针对的对象是想要全面了解算法竞赛内容的入门选手,想要单纯研习算法的同学可以啃啃《算法导论》,ACM的大神们加油消灭掉刘汝佳等人的大黑书吧~~

  刚刚入门的孩纸们要和我一起fighting啊= =~~



  话不多说,进入正题咯~, (本节部分概念来源本书P25-2.1.3 堆,其余均为原创)

  堆的概念:

    数据结构中所说的堆(heap)指的就是一个完全二叉树,当然可以用链表来实现,也可以用一维数组(线性)来模拟实现。

    依照堆中存放的数据大小,堆分为两大类,一类是最大堆,一类是最小堆。

  • 最大堆:任意一个结点的值都大于等于任一子结点的值,所以最大堆的根(root)一定是maximun。
  • 最小堆:任意一个结点的值都小于等于任一子结点的值,所以最小堆的根(root)一定是minimun。


  堆的实现

  我们经常听说,heap是一种高效紧凑的数据结构,那么为什么高效而紧凑呢。用一张图来简单介绍吧。(下图中 上下分别为heap数组(用heap[]表示),heap的图示)

    

    ps:上图中的完全二叉树可以作为heap的图示,上面绿色一栏是对应的数组(array),例如16就是heap[1],14就是heap[2]...依次类推。

    我们习惯上把 14 和 10 叫做 16 的子结点,14为16的左儿子,10为16的右儿子。

    那么像这样,我们就可以从数组(array)中得到heap[2],heap[3]为heap[1]的子结点,heap[4],heap[5]为heap[2]的子结点....

      通过c/c++整形除法规则,得到2/2 = 1 , 3/2 = 1;因此我们把 数据所在位置 满足 s/2 =f 公式的 s 称作 f 的子结点(son), f 称作 s 的父结点(father),这样我们就可以利用数组来紧凑整齐地存储这一系列数据,下一次要调用某一位置 p 的父结点时,直接采用p/2就可以找到 p 的父结点了,同理,子结点就是p*2和p*2+1,这样存储数据是不是很整齐也很便于查找呢。(虽然小编觉得手写这个数据结构的功能时依然会有些繁琐啦= =)

   



   堆的操作:

   那么下面我们来看一下这个数据结构的一般操作怎样通过代码实现呢?(多代码预警~~)(入门的孩纸们记得多调试就容易理解了~~fighting!)

  • 删除优先级最高的元素-DeleteMin()  ——  例如删除-最小堆的heap[1]

    此操作分为三步:

  1. 直接删除根(root);
  2. 用最后一个元素代替root;
  3. 将heap向下重新调整;————第三步表示为下方被调用的 调整堆函数 - down()

 1 /* 删除优先级最高的元素 */
 2 /*        最小堆为例        */
 3
 4 /* heap - down_adjustment */
 5 void down(int p)    //current_node
 6 {
 7     int q = p*2;    //left_son_node
 8     int a = heap[p];
 9
10     while (q < hlength)        //hlength指的是heap数组的长,也就是堆中元素总数
11     {
12         if(heap[q] > heap[q+1])    //find_min_son
13             q++;
14
15         if(heap[q] < a)    //complete_adjustment
16             break;
17         else
18         {
19             heap[p] = heap[q];
20             p = q;
21             q = p*2;
22         }
23     }
24     heap[p] = a;
25     return;
26 }
27
28 /* delete_minimun_node */
29 int DleteMin()
30 {
31     int r = heap[1];        //delete_root
32     heap[1] = heap[hlength--];
33     down(1);        //this is the key point!!
34     return r;
35 }

View Heap-Code

  • 在堆中插入新元素-Insert(x)——依然以最小堆为例  (不懂的依然记得一步一步地来理解,最好自己调试)

    操作步骤为:

  1. 将待insert的元素x添加到末尾;
  2. 向上调整;————第二步用被调用的 up() 函数表示;

 1 /* 堆中插入新元素 */
 2 /*     最小堆为例      */
 3
 4 /* heap - up_adjustment */
 5 void up(int p)        //current_node
 6 {
 7     int q = p/2;        //partner_node
 8     int a = heap[p];
 9
10     while(q > 1 && a < heap[q])
11     {
12         heap[p] = heap[q];
13         p = q;
14         q = p/2;
15     }
16     heap[p] = a;
17     return;
18 }
19
20 /* Insert_new_node */
21 void Insert(int a)
22 {
23     heap[++hlength] = a;    //加长并将a加到末尾
24     up(hlength);
25 }

View Heap-Code

  •  将x位置的优先级提升到 p 值:IncreaseKey(x,p);

1 /* 堆中将x优先级提至p */
2 void IncreaseKey(int x,int p)
3 {
4     if (heap[x] < p)    //若heap[x]本身小于p,那么x的优先级本来就比p高
5         return;
6     heap[x] = p;        //否则将heap[x]赋值为 p
7     up(x);        //调用上方函数up()
8 }

View Heap-Code

  • 数组模拟建堆:Build()——(⊙o⊙)额,原谅我最后才建堆,其实这也是正常顺序啦= =

1 /* 数组建堆 */
2 void Build()
3 {
4     for (int i = hlength / 2; i > 0; i++)
5         down(i);    //调用第一次的 调整堆函数
6 }

View Build_heap-Code


  堆的时间度分析:

  • 向上和向下调整每层都是常数级别,共log n层,因此 调整堆 的时间度O(log n);
  • 插入/删除 只调用一次向上或向下调整,因此都是O(log n);

    现在大家明白为什么堆的时间效率如此高了吧~~


  嗯,就是这样了= =,借此希望记录下 某一种 我的大学,也希望能给眼下正在默默刷题的ACM新人们 or 算法入门新人们一些建议和一些相关整理,希望我没有误人子弟就好啦~

  那么,fighting ~~

——————————From 小墨

时间: 08-06

《ACM/ICPC 算法训练教程》读书笔记一之数据结构(堆)的相关文章

《ACM/ICPC 算法训练教程》读书笔记 之 数据结构(线段树详解)

依然延续第一篇读书笔记,这一篇是基于<ACM/ICPC 算法训练教程>上关于线段树的讲解的总结和修改(这本书在线段树这里Error非常多),但是总体来说这本书关于具体算法的讲解和案例都是不错的. 线段树简介 这是一种二叉搜索树,类似于区间树,是一种描述线段的树形数据结构,也是ACMer必学的一种数据结构,主要用于查询对一段数据的处理和存储查询,对时间度的优化也是较为明显的,优化后的时间复杂为O(logN).此外,线段树还可以拓展为点树,ZWK线段树等等,与此类似的还有树状数组等等. 例如:要将

程序语言的奥妙:算法解读 &mdash;&mdash;读书笔记

算法(Algorithm) 是利用计算机解决问题的处理步骤. 算法是古老的智慧.如<孙子兵法>,是打胜仗的算法. 算法是古老智慧的结晶,是程序的范本. 学习算法才能编写出高质量的程序. 懂得了算法,游戏水平会更高. 比如下棋,如果懂得棋谱,就不需要每次考虑"寻找最好的一步棋",按照棋谱 就可以走出最好的几步棋.棋谱是先人们智慧的结果,因此掌握多种棋谱的人更 容易在对弈中获得胜利. 算法的学习类似学习游戏攻略. 算法是编写好程序的"棋谱". 算法必须满足&

算法导论读书笔记之钢条切割问题

算法导论读书笔记之钢条切割问题 巧若拙(欢迎转载,但请注明出处:http://blog.csdn.net/qiaoruozhuo) 给定一段长度为n英寸的钢条和一个价格表 pi (i=1,2, -,n),求切割钢条的方案,使得销售收益rn最大.注意,如果长度为n英寸的钢条价格pn足够大,最优解可能就是完全不需要切割. 若钢条的长度为i,则钢条的价格为Pi,如何对给定长度的钢条进行切割能得到最大收益? 长度i   1   2    3   4     5      6     7     8  

算法导论读书笔记(15) - 红黑树的具体实现

算法导论读书笔记(15) - 红黑树的具体实现 目录 红黑树的简单Java实现 红黑树的简单Java实现 /** * 红黑树 * * 部分代码参考自TreeMap源码 */ public class RedBlackTree<T> { protected TreeNode<T> root = null; private final Comparator<? super T> comparator; private int size = 0; private static

ACM/ICPC算法训练 之 数学很重要-浅谈“排列计数” (DP题-POJ1037)

这一题是最近在看Coursera的<算法与设计>的公开课时看到的一道较难的DP例题,之所以写下来,一方面是因为DP的状态我想了很久才想明白,所以借此记录,另一方面是看到这一题有运用到 排列计数 的方法,虽然排列计数的思路简单,但却是算法中一个数学优化的点睛之笔. Poj1037  A decorative fence 题意:有K组数据(1~100),每组数据给出总木棒数N(1~20)和一个排列数C(64位整型范围内),N个木棒长度各异,按照以下条件排列,并将所有可能结果进行字典序排序 1.每一

算法导论读书笔记(17)

算法导论读书笔记(17) 目录 动态规划概述 钢条切割 自顶向下的递归实现 使用动态规划解决钢条切割问题 子问题图 重构解 钢条切割问题的简单Java实现 动态规划概述 和分治法一样, 动态规划 (dynamic programming)是通过组合子问题的解而解决整个问题的.分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解而得到原问题的解.与此不同,动态规划适用于子问题并不独立的情况,即各子问题包含公共的子子问题.在这种情况下,分治法会重复地求解公共的子子问题.而动态

算法导论读书笔记(16)

算法导论读书笔记(16) 目录 动态顺序统计 检索具有给定排序的元素 确定一个元素的秩 区间树 步骤1:基础数据结构 步骤2:附加信息 步骤3:维护信息 步骤4:设计新操作 动态顺序统计 之前介绍过 顺序统计 的概念.在一个无序的集合中,任意的顺序统计量都可以在 O ( n )时间内找到.而这里我们将介绍如何在 O ( lg n )时间内确定任意的顺序统计量. 下图显示的是一种支持快速顺序统计量操作的数据结构.一棵 顺序统计树 T 通过在红黑树的每个结点中存入附加信息而成.在一个结点 x 内,增

算法导论读书笔记(14) - 二叉查找树的具体实现

算法导论读书笔记(14) - 二叉查找树的具体实现 目录 二叉查找树的简单Java实现 二叉查找树的简单Java实现 /** * 二叉查找树 * 部分代码参考自TreeMap的源码 */ public class BinarySearchTree<T> { protected TreeNode<T> root = null; private final Comparator<? super T> comparator; private int size = 0; pub

算法导论读书笔记(13)

算法导论读书笔记(13) 目录 红黑树 旋转 插入 情况1 : z 的叔父结点 y 是红色的 情况2 : z 的叔父结点 y 是黑色的,而且 z 是右孩子 情况3 : z 的叔父结点 y 是黑色的,而且 z 是左孩子 删除 情况1 : x 的兄弟 w 是红色的 情况2 : x 的兄弟 w 是黑色的,且 w 的两个孩子都是黑色的 情况3 : x 的兄弟 w 是黑色的, w 的左孩子是红色的,右孩子是黑色的 情况4 : x 的兄弟 w 是黑色的,且 w 的右孩子是红色的 红黑树 红黑树 是一种二叉查