Skip to content

Commit 90210bf

Browse files
coderbruiscoderbruis
committed
添加堆和优先队列文章
1 parent 1d0a76f commit 90210bf

4 files changed

Lines changed: 70 additions & 6 deletions

File tree

‎README.md‎

Lines changed: 19 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,25 @@
22

33
本项目主要用于自己在工作之余记录用Java实现的算法和数据结构的源码；同时还会记录自己刷leetcode的题解思路等；
44

5+
# 经典排序算法
6+
7+
- [经典排序算法](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%9F%BA%E7%A1%80%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
8+
9+
# 经典数据结构
10+
11+
- [数组]()
12+
- [栈和队列]()
13+
- [链表]()
14+
- [二分搜索树]()
15+
- [集合和映射]()
16+
- [堆和优先队列]()
17+
- [线段树]()
18+
- [Trie]()
19+
- [并查集]()
20+
- [AVL]()
21+
- [红黑树]()
22+
- [哈希表]()
23+
524
# leetcode专区
625

726
## 1. 数组
@@ -26,10 +45,4 @@
2645
## 3. 链表
2746

2847

29-
# 经典排序算法
30-
31-
- [经典排序算法](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%9F%BA%E7%A1%80%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
32-
33-
# 数据结构
34-
3548
==================== 持续更新 ===================

‎notes/datastructures/堆和优先队列.md‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
2+
# 前言
3+
4+
下面先了解下二叉堆的基础知识
5+
6+
## 1. 二叉堆
7+
8+
二叉堆是一棵完全二叉树，如下图：
9+
![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heapandpriorityqueue01.png)
10+
11+
这里，给出一个最大堆和最小堆的定义：
12+
13+
**最大堆**
14+
15+
> 堆中某个节点的值总是不大于其父节点的值
16+
17+
**最小堆**
18+
19+
> 堆中某个节点的值总是不小于其父节点的值
20+
21+
### 1.1 用数组存储二叉堆
22+
23+
如将下列数组存储为二叉堆：
24+
25+
```
26+
[62, 41, 30, 28, 16, 22, 13, 19, 17, 15]
27+
0 1 2 3 4 5 6 7 8 9
28+
```
29+
将数组转化为二叉堆：
30+
![二叉堆图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/heapandpriorityqueue02.png)
31+
32+
对于上面的二叉堆，有以下三个比较重要的公式：
33+
34+
```
35+
parent(i) = (i - 1) / 2 求当前节点的父节点的索引
36+
left child(i) = 2 * i + 1 求当前节点的左子节点的索引
37+
right child(i) = 2 * i + 2 求当前节点的右子节点的索引
38+
```
39+
40+
## 2. 优先队列
41+
42+
普通线性结构和顺序线性结构对比
43+
| | 入队 | 出队（拿出最大元素） |
44+
| :----: | :-----: | :--------: |
45+
| 普通线性结构 | O(1) | O(n) |
46+
| 顺序线性结构 | O(n) | O(1) |
47+
| 堆 | O(logn) | O(logn) |
48+
49+
**普通线性结构**入队O(1)分析，因为入队不考虑顺序性，所以排在队尾即可。
50+
51+
**顺序线性结构**入队O(n)分析，入队需要考虑顺序性，需要进行调度。

‎notes/pictures/heapandpriorityqueue01.png‎

11.8 KB
Loading

‎notes/pictures/heapandpriorityqueue02.png‎

11.8 KB
Loading

0 commit comments

Comments
 (0)