一、堆的定义
堆（Heap）是一种特殊的完全二叉树数据结构。分为最大堆和最小堆。
最大堆中，每个节点的值都大于等于其子节点的值；最小堆中，每个节点的值都小于等于其子节点的值。
二、堆的基本操作
-
插入元素（Insert）：
- 将新元素插入到堆的末尾。
- 然后通过不断比较新元素与其父节点的值，进行上滤操作，直到满足堆的性质。
- 时间复杂度为 O (log n)，其中 n 是堆中元素的个数。
-
删除根节点（Delete Root）：
- 通常删除的是根节点，因为在最大堆中根节点是最大值，在最小堆中根节点是最小值。
- 用堆的最后一个元素替换根节点。
- 然后对新的根节点进行下滤操作，使其满足堆的性质。
- 时间复杂度为 O (log n)。
-
获取根节点（Get Root）：
- 直接返回堆的根节点的值，时间复杂度为 O (1)。
-
堆化（Heapify）：
- 给定一个数组，可以将其转换为堆。
- 从最后一个非叶节点开始，对每个非叶节点进行下滤操作，直到根节点。
- 时间复杂度为 O (n)，其中 n 是数组的长度。
三、代码实现
以下是用 Java 语言实现最大堆的代码示例：
class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int capacity) {
heap = new int[capacity];
size = 0;
}
public void insert(int value) {
if (size == heap.length) {
throw new IllegalStateException("Heap is full");
}
heap[size] = value;
int index = size;
while (index > 0 && heap[index] > heap[parent(index)]) {
swap(index, parent(index));
index = parent(index);
}
size++;
}
public int deleteMax() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int max = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return max;
}
private int parent(int index) {
return (index - 1) / 2;
}
private int leftChild(int index) {
return 2 * index + 1;
}
private int rightChild(int index) {
return 2 * index + 2;
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private void heapify(int index) {
int largest = index;
int left = leftChild(index);
int right = rightChild(index);
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest!= index) {
swap(index, largest);
heapify(largest);
}
}
}
public class HeapExample {
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(30);
maxHeap.insert(8);
maxHeap.insert(15);
System.out.println("删除最大值：" + maxHeap.deleteMax());
System.out.println("删除最大值：" + maxHeap.deleteMax());
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
评论（0）