推荐:kuan

欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。

推荐:kuan

IDEA,Mac,Alfred,electerm,Git,typora,apifox

mysql

问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

欢迎订阅本专栏

堆Heap是一种重要的数据结构通常用于实现优先队列和一些其他算法。

堆具有以下主要特点

完全二叉树结构

堆通常是一个完全二叉树这意味着树中的每个节点都有最多两个子节点除了最后一层其他层都是满的。

这种特性使得堆可以有效地使用数组来表示因为数组的索引操作非常高效。

堆序性质

堆分为两种主要类型最小堆和最大堆它们都具有堆序性质。

在最小堆中每个节点的值都小于或等于其子节点的值根节点的值最小。

在最大堆中每个节点的值都大于或等于其子节点的值根节点的值最大。

堆支持一些基本操作包括插入元素、删除根节点最小或最大元素、查找根节点最小或最大元素以及堆化操作将一个无序数组或树转化为堆。

这些操作的时间复杂度通常为

O(log

堆广泛用于解决各种问题如优先队列用于任务调度、Dijkstra

算法等、堆排序算法、求中位数、Top

算法中的最小生成树等等。

由于其高效的插入和删除操作堆在这些问题中表现出色。

0对于节点

2。

这种表示方法使得堆的操作更加高效。

堆可以是最小堆或最大堆具体类型取决于问题需求。

平衡性

堆是一种自平衡数据结构即在插入和删除操作后堆仍然保持堆序性质。

这是通过堆化操作来实现的它可以向上上滤或向下下滤调整节点的位置以满足堆的要求。

堆是一种非常有用的数据结构用于解决许多与优先级相关的问题和算法。

最小堆和最大堆的差异在于它们的堆序性质但它们都具有相似的操作和实现方式。

理解堆的基本原理和操作对于编写高效的算法非常重要。

2.大顶堆

1);//容量--size--;//堆顶下沉down(0);return

top;}/***

MaxHeap(array);System.out.println(Arrays.toString(maxHeap.array));}

}3.小顶堆

\sum_{i1}^{h}(\frac{2^h}{2^i}*(i-1))

i1∑h​(2i2h​∗(i−1))

Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]推导出

2^h

建立大顶堆将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆重复第二步直至堆里剩一个元素

int[]

System.out.println(Arrays.toString(maxHeap.array));

while

{//交换堆顶和堆底,把最大的移到堆底maxHeap.swap(0,

maxHeap.size

1);//将堆底的元素排除maxHeap.size--;//堆顶的元素需要下沉maxHeap.down(0);

System.out.println(Arrays.toString(maxHeap.array));2.数组中第

大元素-力扣

heap.peek()){heap.replace(numbers[i]);}}return

heap.peek();

{//小顶堆,先加入2个PriorityQueueInteger

queue

{queue.add(numbers[i]);}//再加入后面剩下的for

(int

{queue.poll();queue.add(numbers[i]);}}return

queue.peek();

{if(!heap.isFull()){heap.offer(val);}

else

heap.peek()){heap.replace(val);}return

private

{queue.poll();queue.offer(val);}return

queue.peek();

{grow();}up(offered);size;}private

void

int[capacity];System.arraycopy(array,

0,newArray,

true);/**为了保证两边数据量的平衡ulli两边数据一样时,加入左边/lili两边数据不一样时,加入右边/li/ul但是,

public

{right.offer(num);left.offer(right.poll());}

else

{left.offer(num);right.offer(left.poll());}

}/***

{right.offer(num);left.offer(right.poll());}

else

{left.offer(num);right.offer(left.poll());}

}/***