二叉堆
二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆
◼️ 鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可
◼️ 索引 i 的规律( n 是元素数量)
如果 i = 0 ,它是根节点
如果 i > 0 ,它的父节点的索引为 floor( (i – 1) / 2 ) (向下取整)
如果 2i + 1 ≤ n – 1,它的左子节点的索引为 2i + 1
如果 2i + 1 > n – 1 ,它无左子节点
文章来源:https://www.toymoban.com/news/detail-733611.html
如果 2i + 2 ≤ n – 1 ,它的右子节点的索引为 2i + 2
如果 2i + 2 > n – 1 ,它无右子节点
文章来源地址https://www.toymoban.com/news/detail-733611.html
大根堆的例子
public class HeapSort {
public static void main(String[] args) {
System.out.println("大顶堆测试");
int[] arr = {68, 72, 43, 50, 38, 10, 90, 65};
MyHeapSort obj = new MyHeapSort();
for (int i : arr) {
obj.add(i);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = obj.remove();
}
System.out.println("堆排序后:");
for (int i : arr) {
System.out.print(i + " ");
}
// 90 72 68 65 50 43 38 10
System.out.println();
for (int i : arr) { //堆空了,重新添加元素进去
obj.add(i);
}
System.out.println("获取堆顶元素:" + obj.get());
System.out.println("替换堆顶元素为13:" + obj.replace(13));
System.out.println("替换堆顶元素为13后的堆顶元素:" + obj.get());
}
static class MyHeapSort { //大根heap 由大到小的排序
public int[] arr;
public int size;
public int defaultSize = 10;
public MyHeapSort() {
size = 0;
arr = new int[defaultSize];
}
//扩容代码
public void ensureCap(int cap) {
int oldcap = arr.length;
if (oldcap >= cap) return;
//新容量为旧容量的1.5倍
int newcap = oldcap + oldcap >> 1;
int[] newarr = new int[newcap];
for (int i = 0; i < size; i++) {
newarr[i] = arr[i];
}
arr = newarr;
}
public void add(int val) {
ensureCap(size + 1);
arr[size++] = val;
shiftup(size - 1);
}
//上滤
public void shiftup(int index) {
int cur = arr[index];
while (index > 0) {
int pindex = (index - 1) / 2;
int parent = arr[pindex];
if (parent >= cur) break;
arr[index] = parent;
index = pindex;
}
arr[index] = cur;
}
//删除:二叉堆的删除是删除堆顶元素
//思路:最后一个元素代替堆顶元素,删除最后一个元素,然后下窜
public int remove() {
int last = --size;
int root = arr[0];
arr[0] = arr[last];
//arr[last] 不用管了,因为长度要减1,减1后,最后一个元素也不存在了
shiftdown(0);
return root;
}
public void shiftdown(int index) {
int half = size >> 1;
int root = arr[0];
while (index < half) {
//index:只有左子节点,或者左右子节点都有
int pos = (index << 1) + 1;
int child = arr[pos];
int right = pos + 1;
if (right < size && arr[right] > arr[pos]) {
pos = right;
child = arr[right];
}
if (root > child) break;
arr[index] = child;
index = pos;
}
arr[index] = root;
}
public int get() { //获取堆顶元素
if (size == 0) return Integer.MIN_VALUE;
return arr[0];
}
//删除堆顶的元素的同时,插入一个新元素
public int replace(int ele) { //替换堆顶元素
int root = Integer.MIN_VALUE;
if (size == 0) {
arr[0] = ele;
size++;
} else {
root = arr[0];
arr[0] = ele;
shiftdown(0);
}
return root;
}
}
}
/*
大顶堆测试
堆排序后:
90 72 68 65 50 43 38 10
获取堆顶元素:90
替换堆顶元素为13:90
替换堆顶元素为13后的堆顶元素:72
*/
到了这里,关于算法基础:堆【以大根堆为例】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!