算法学习：堆
2023-12-13 本文已影响0人
alex很累
基本概念
堆（Heap）是一种基于完全二叉树的数据结构，用于维护一些元素集合中的最大值或最小值。
完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都集中在左部连续位置；
堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值；
每个节点都大于等于其子树节点的堆叫“大顶堆“，根是最大值；
每个节点都小于等于其子树节点的堆叫“小顶堆“，根是最小值。
堆的存储表示
因为堆是一种完全二叉树，我们可以用数组来表示它。
并且具有以下规律：
- i 结点的父结点
par = floor((i-1)/2)「向下取整」; - i 结点的左子结点
2 * i +1; - i 结点的右子结点
2 * i + 2。
堆的操作
1.堆化
在插入或删除操作后需要进行调整，让其重新满足堆的特性，这个调整的过程叫做堆化（heapify）。
- 从下往上的堆化（上浮）
当前元素不断向上和父节点比较大小；例如，如果是大顶堆，当前元素比父节点大，交换。 - 从上往下的堆化（下沉）
当前元素不断向下和两个孩子节点比较大小；例如，如果是大顶堆，当前元素与子节点中较大的比，比子节点小交换。
2.插入元素
插入操作是将新元素插入到堆的末尾，然后通过上浮操作将其移动到正确的位置,时间复杂度是O(log n)。
3.删除堆顶元素
删除操作是将堆顶元素删除，并将堆的最后一个元素移动到堆顶，然后通过下滤操作将其移动到正确的位置，时间复杂度是O(log n)。
4.获取最大值/最小值
获取最值操作则是返回堆顶元素的值，而不删除它,时间复杂度O(1)。
