Black Box(堆)

2017年10月29日360

Black Box

对问题的分析设计过程

题目要求实现一个支持插入序列和在第$i$次查询序列第$i$小的数的算法,经过思考得到如下算法:

  1. 可以考虑直接用动态开节点的线段树或者BST来进行在线查询
  2. 若将序列分成前$i$小和其他,可以通过两个堆实现单次操作在$O(\log n)$的时间内的在线查询和修改
  3. 若使用时间倒流方法,将插入和删除离线从后向前处理,可以只使用两个栈实现上述操作

程序中用到的数据机构和算法

综合考虑到实现难度和时间空间复杂度,考虑用第二种方法实现。通过维护一个大根堆存储前i小的元素以及一个小根堆存储其他元素。对操作有如下实现方法:

  • 添加元素$x$
    • 元素$x$小于第$i$个元素:将元素$x$插入大根堆中,并将大根堆堆顶元素插入小根堆中。
    • 元素$x$大于第$i$个元素:将元素$x$插入小根堆中。
  • 查询输出大根堆堆顶元素,将小根堆堆顶元素插入大根堆中

程序的运行情况

提交一次即通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 使用STL库将会大大减少代码复杂度
  2. 注意初始化问题

Code:

 

%d 博主赞过: