Data structure - heap
数据结构 - 堆
Implement a binary heap
heap is a data structure
- 必须是一颗完全二叉树
heap 分类
- max heap(大顶堆): 父亲大孩子小
- min heap(小顶堆): 父亲小孩子大
heap的插入
- heap的插入在
last position
- last postion位置的寻找: 从上到下,从坐到右
- heap在每次插入后,都要调整,插入后和父亲比较。
- if smaller than parent(min heap), then bubble it up.
- heap的插入在
heap的删除
- remove the highest element, then put the element at last position to the top.
下边来完成一次手动模拟, 步骤如下所示:
1 | insert(4); |
- 第一步,向一棵空树中插入值为
4
的结点 - 第二步,向树中插入值为
10
的结点 - 第三步,向树中插入值为
15
的结点 - 移除结点
- 在第三步基础上插入值为
0
的结点
Insert an element: insert into the last position and bubble it up.
Remove an element: remove the highest element and put the element at last position to the top, then bubble it down.
时间复杂度
- insert: $\color{ blue }{O(logn)}$
- removal: $\color{blue}{O(logn)}$
其实可以理解为树的高度,因为完全二叉树的高度为$\lceil{log_2(n+1)}\rceil$, 其时间复杂度可以认为是$O(log_2n)$。