看动画轻松理解「 堆 」
堆(heap)又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。
因为队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。
而堆虽然在堆底插入元素,在堆顶取出元素,但是堆中元素的排列不是按照到来的先后顺序,而是按照一定的优先顺序排列的。
本文通过堆的实现、最小堆(最大堆)、堆的时间复杂度、优先队列的实现、堆排序来介绍「 堆 」。
堆的实现
堆的一个经典的实现是完全二叉树(complete binary tree),这样实现的堆称为二叉堆(binary heap)。
这里来说明一下满二叉树的概念与完全二叉树的概念。
满二叉树:除了叶子节点,所有的节点的左右孩子都不为空,就是一棵满二叉树,如下图。
可以看出:满二叉树所有的节点都拥有左孩子,又拥有右孩子。
完全二叉树:不一定是一个满二叉树,但它不满的那部分一定在右下侧,如下图
堆的特性:
- 必须是完全二叉树
- 任一结点的值是其子树所有结点的最大值或最小值
- 最大值时,称为“最大堆”,也称大顶堆;
- 最小值时,称为“最小堆”,也称小顶堆。
堆的基础实现
只要谨记堆的定义特性,实现起来其实是很容易的。
- 特性1. 维持完全二叉树
- 特性2. 子类数字总是大于父类数字
1public class MinHeap <E extends Comparable<E>> { 2 private Array<E> data; 3 4 public MinHeap(int capacity){ 5 data = new Array<>(capacity); 6 } 7 8 public MinHeap(){ 9 data = new Array<>(); 10 } 11 12 // 返回堆中的元素个数 13 public int size(){ 14 return data.getSize(); 15 } 16 17 // 返回一个布尔值, 表示堆中是否为空 18 public boolean isEmpty(){ 19 return data.isEmpty(); 20 } 21 22 // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引 23 private int parent(int index){ 24 return (index - 1) / 2; 25 } 26 27 // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引 28 private int leftChild(int index){ 29 return index * 2 + 1; 30 } 31 32 // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引 33 private int rightChild(int index){ 34 return index * 2 + 2; 35 } 36}
最小堆的插入(ADD)
假设现有元素 5 需要插入,为了维持完全二叉树的特性,新插入的元素一定是放在结点 6 的右子树;同时为了满足任一结点的值要小于左右子树的值这一特性,新插入的元素要和其父结点作比较,如果比父结点小,就要把父结点拉下来顶替当前结点的位置,自己则依次不断向上寻找,找到比自己大的父结点就拉下来,直到没有符合条件的值为止。
动画讲解:
- 在这里先将元素 5 插入到末尾,即放在结点 6 的右子树。
然后与父类比较, 6 > 5 ,父类数字大于子类数字,子类与父类交换。
重复此操作,直到不发生替换。
Show me the code:
添加一个辅助函数,用来交换传入的索引两个位置的元素值
1/** 2 * 交换传入的索引两个位置的元素值 3 * 4 * @param i 5 * @param j 6 */ 7 public void swap(int i, int j) { 8 if (i < 0 || i >= size || j < 0 || j >= size) 9 throw new IllegalArgumentException("Index is illegal."); 10 11 E temp = data[i]; 12 data[i] = data[j]; 13 data[j] = temp; 14 }
数组中添加交换两元素位置的方法,注意下面代码中注释的描述特性位置。
1 /** 2 * 堆中添加元素方法。 3 * 4 * @param e 5 */ 6 public void add(E e) { 7 //特性1:新插入的元素首先放在数组最后,保持完全二叉树的特性 8 data.addLast(e); 9 siftUp(data.getSize() - 1); 10 } 11 12 /** 13 * index 为i位置元素上浮。 14 * 15 * @param i 16 */ 17 private void siftUp(int i) { 18 //特性2:比较插入值和其父结点的大小关系,小于父结点则用父结点替换当前值,index位置上升为父结点 19 // 当上浮元素大于父亲,继续上浮。并且不能上浮到0之上 20 // 直到i 等于 0 或 比 父亲节点小了。 21 while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) { 22 // 数组Array中添加方法swap 23 data.swap(i, parent(i)); 24 i = parent(i); // 这句话让i来到新的位置,使得循环可以查看新的位置是否还要大。 25 } 26 }
最小堆的删除(DELETE)
核心点:将最后一个元素填充到堆顶,然后不断的下沉这个元素。
假设要从节点 1 ,也可以称为取出节点 1 ,为了维持完全二叉树的特性 ,我们将最后一个元素 6 去替代这个 1 ;然后比较 1 和其子树的大小关系,如果比左右子树大(如果存在的话),就要从左右子树中找一个较小的值替换它,而它能自己就要跑到对应子树的位置,再次循环这种操作,直到没有子树比它小。
通过这样的操作,堆依然是堆,总结一下:
- 找到要删除的节点(取出的节点)在数组中的位置
- 用数组中最后一个元素替代这个位置的元素
- 当前位置和其左右子树比较,保证符合最小堆的节点间规则
- 删除最后一个元素
Show me the code:
1 public E findMin() { 2 return data.get(0); 3 } 4 5 public E extractMin() { 6 7 E ret = findMin(); 8 9 data.swap(0, data.getSize() - 1); // 0位置元素和最后一个元素互换。 10 data.removeLast(); // 删除此时的最后一个元素(最小值) 11 siftDown(0); // 对于0处进行siftDown操作 12 13 return ret; 14 } 15 16 /** 17 * k位置元素下移 18 * 19 * @param k 20 */ 21 private void siftDown(int k) { 22 23 while(leftChild(k) < data.getSize()){ 24 int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置 25 if( j + 1 < data.getSize() && 26 data.get(j + 1).compareTo(data.get(j)) < 0 ) 27 j ++; 28 // data[j] 是 leftChild 和 rightChild 中的最小值 29 30 if(data.get(k).compareTo(data.get(j)) >= 0 ) 31 break; 32 33 data.swap(k, j); 34 k = j; 35 } 36 }
时间复杂度
对于有 n 个节点的堆来说,其高度 d = log2n + 1
。 根为第 0 层,则第 i 层结点个数为 2i,
考虑一个元素在堆中向下移动的距离。
- 大约一半的结点深度为 d-1 ,不移动(叶)。
- 四分之一的结点深度为 d-2 ,而它们至多能向下移动一层。
- 树中每向上一层,结点的数目为前一层的一半,而子树高度加一
堆有logn
层深,所以插入删除的平均时间和最差时间都是O(logN)
优先队列(priority_queue)
普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构,比如每次取值都取最大的元素。
优先队列支持下面的操作:
- a. 找出优先级最高的元素(最大或最小元素);
- b. 删除一个具有最高优先级的元素;
- c. 添加一个元素到集合中。
代码实现
1public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { 2 3 private MaxHeap<E> maxHeap; 4 5 public PriorityQueue(){ 6 maxHeap = new MaxHeap<>(); 7 } 8 9 @Override 10 public int getSize(){ 11 return maxHeap.size(); 12 } 13 14 @Override 15 public boolean isEmpty(){ 16 return maxHeap.isEmpty(); 17 } 18 19 @Override 20 public E getFront(){ 21 return maxHeap.findMax(); 22 } 23 24 @Override 25 public void enqueue(E e){ 26 maxHeap.add(e); 27 } 28 29 @Override 30 public E dequeue(){ 31 return maxHeap.extractMax(); 32 } 33}
堆排序
理解了优先队列,堆排序的逻辑十分简单。
第一步:让数组形成堆有序状态;
第二步:把堆顶的元素放到数组最末尾,末尾的放到堆顶,在剩下的元素中下沉到正确位置,重复操作即可。
堆排序动画
原文地址:https://www.cnblogs.com/fivestudy/p/10156721.html
相关推荐
-
测试了一下编解码的执行效果 Java基础
2019-8-20
-
Java 添加、读取、删除和重置Excel图片 Java基础
2020-6-13
-
ItemTouchHelper之SwipeDismiss Java基础
2019-8-22
-
死磕 java集合之ConcurrentHashMap源码分析(一) Java基础
2020-5-28
-
SSM(六)跨域传输 Java基础
2020-5-30
-
Spring事务在多线程下保证原子性 Java基础
2020-6-14
-
java中的Queue接口 Java基础
2020-6-13
-
java多线程3:原子性,可见性,有序性 Java基础
2020-6-13
-
Restful API 中的错误处理 Java基础
2019-8-9
-
MongoDB中_class字段的作用 Java基础
2019-8-18