目录
9.1.概述
9.2.操作
9.2.1.插入
9.2.2.删除
9.2.3.代码实现
9.1.概述
概念:
根节点是自己所在子树中的最值的完全二叉树。
根节点是所在子树的最大值,称为大顶堆。
根节点是所在子树的最小值,称为小顶堆。
堆的任何子树的根节点到子树上的任意节点,路径上的节点都是有序的,大顶堆为降序,小顶堆为升序。
此处展示一个大顶堆:
作用:
堆一般用来在大量数据中找到前N大或者前N小的数据。
存储:
一般用数组来存储堆,首先因为堆一般是从空树开始建立的,不论如何操作其一定会是一颗完全二叉树,不存在大量非叶子结点没有左右孩子的情况,所以用数组来表示不会造成内存浪费。其次堆的删除操作需要从叶节点反向向根结点方向遍历,链表结构不太好支持这种反向遍历。
9.2.操作
9.2.1.插入
堆的插入采用尾插法,新入堆的节点挂在最后一个叶节点上,然后往上浮(交换位置)。
假设已有一颗树,是按照44、25、31、18、10的插入顺序建树的。
假设插入的是20:
假设插入的是35:
9.2.2.删除
堆的删除操作,从叶子结点开始删除的话,直接删除即可,不会有任何影响,只有在删除非叶子结点时才要考虑进行结点间的调整,保持堆是大顶堆或者小顶堆。
堆在使用时每次弹出的都是堆顶的数据,因此删除操作都是针对堆顶元素的,此处以大顶堆的删除操作为例:文章来源:https://www.toymoban.com/news/detail-462483.html
用最末尾的叶节点替换根节点,然后新的根节点与左右孩子比较是否为最大值,若不为最大值,则与参与比较的三个节点中的最大值互换位置,然后递归以上过程,出口为到达叶节点或者到达合适位置。文章来源地址https://www.toymoban.com/news/detail-462483.html
9.2.3.代码实现
package linearStructure.tree.heap;
import java.util.ArrayList;
import java.util.List;
public class MaxTopHeap {
//存储堆的数组
private int[] heap;
//堆的最大存储容量
private int maxSize;
//当前堆的存储数量
private int heapSize;
public MaxTopHeap(int maxSize) {
this.heap = new int[maxSize];
this.maxSize = maxSize;
this.heapSize = 0;
}
// 判断是否为空的方法
public boolean isEmpty() {
return heapSize == 0;
}
// 判断是否填满
public boolean isFull() {
return heapSize == maxSize;
}
// 获取堆顶的值
public int peek() throws Exception {
if (heapSize == 0) {
throw new Exception("heap is empty");
}
return heap[0];
}
// 往堆中添加值
public void insert (int value) throws Exception {
if (heapSize == maxSize) {
throw new Exception("head is full");
}
heap[heapSize] = value;
heapSize++;
buildMaxHeap(heap);
}
// 删除堆顶值
public int poll() throws Exception {
if (heapSize == 0) {
throw new Exception("heap is empty");
}
int ans = heap[0];
swap(heap,0,--heapSize);
buildMaxHeap(heap);
return ans;
}
// 建大顶堆
private int[] buildMaxHeap(int[] array) {
for (int i = (heapSize-2)/2; i >= 0; i--) {
adjustDownToUp(array,i,heapSize);
}
return array;
}
private void adjustDownToUp(int[] array, int index, int length) {
int temp = array[index];
for (int i = 2*index+1; i < length; i = 2*i+1) {
if (i < length-1 && array[i] < array[i+1]) {
i++;
}
if (temp >= array[i]) {
break;
} else {
array[index] = array[i];
index = i;
}
}
array[index] = temp;
}
// 交换元素值
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 获取所有元素
public List<Integer> getAllElements() {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < heapSize; i++) {
ans.add(heap[i]);
}
return ans;
}
}
到了这里,关于数据结构(9)树形结构——大顶堆、小顶堆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!