java实现Tree结构，面试中常考，工作中常用，小根堆和大根堆的实现
2024-01-03 04:37:22
java实现Tree结构，面试中常考，工作中常用，小根堆和大根堆的实现
小根堆与大根堆
最小堆（Min Heap）：任何父节点的值都小于或等于其子节点的值。常用于实现优先队列，快速访问最小元素。
最小堆示例
1
/ \
3 2
/ \ / \
5 6 8
public class MinHeap {
/**
* 存储堆元素的数组。
*/
private int[] heap;
/**
* 当前堆中元素的数量。
*/
private int size;
/**
* 堆的最大容量。
*/
private int capacity;
/**
* 构造函数，初始化最小堆。
* @param capacity 堆的初始容量。
*/
public MinHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
/**
* 获取父节点的索引。
* @param i 当前节点的索引。
* @return 父节点的索引。
*/
private int getParentIndex(int i) {
return (i - 1) / 2;
}
/**
* 获取左子节点的索引。
* @param i 当前节点的索引。
* @return 左子节点的索引。
*/
private int getLeftChildIndex(int i) {
return 2 * i + 1;
}
/**
* 获取右子节点的索引。
* @param i 当前节点的索引。
* @return 右子节点的索引。
*/
private int getRightChildIndex(int i) {
return 2 * i + 2;
}
/**
* 判断是否有父节点。
* @param i 当前节点的索引。
* @return 如果有父节点返回 true，否则返回 false。
*/
private boolean hasParent(int i) {
return getParentIndex(i) >= 0;
}
/**
* 判断是否有左子节点。
* @param i 当前节点的索引。
* @return 如果有左子节点返回 true，否则返回 false。
*/
private boolean hasLeftChild(int i) {
return getLeftChildIndex(i) < size;
}
/**
* 判断是否有右子节点。
* @param i 当前节点的索引。
* @return 如果有右子节点返回 true，否则返回 false。
*/
private boolean hasRightChild(int i) {
return getRightChildIndex(i) < size;
}
/**
* 交换堆中两个元素的位置。
* @param i 第一个元素的索引。
* @param j 第二个元素的索引。
*/
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
/**
* 上浮操作，用于保持堆的特性。
*/
private void heapUp() {
int index = size - 1;
while (hasParent(index) && heap[getParentIndex(index)] > heap[index]) {
swap(getParentIndex(index), index);
index = getParentIndex(index);
}
}
/**
* 下沉操作，用于在移除堆顶元素后重建堆。
*/
private void heapDown() {
int index = 0;
while (hasLeftChild(index)) {
int smallerChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && heap[getRightChildIndex(index)] < heap[smallerChildIndex]) {
smallerChildIndex = getRightChildIndex(index);
}
if (heap[index] < heap[smallerChildIndex]) {
break;
} else {
swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
/**
* 向堆中添加新元素。
* @param item 要添加的元素。
*/
public void add(int item) {
if (size == capacity) {
heap = Arrays.copyOf(heap, capacity * 2);
capacity *= 2;
}
heap[size] = item;
size++;
heapUp();
}
/**
* 移除并返回堆顶元素。
* @return 堆顶元素。
*/
public int poll() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int item = heap[0];
heap[0] = heap[size - 1];
size--;
heapDown();
return item;
}
/**
* 返回但不移除堆顶元素。
* @return 堆顶元素。
*/
public int peek() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
return heap[0];
}
/**
* 遍历并返回堆中的所有元素。
* @return 堆中所有元素的列表。
*/
public List<Integer> traverse() {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < size; i++) {
result.add(heap[i]);
}
return result;
}
/**
* 用于演示最小堆的使用。
*/
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(10);
minHeap.add(15);
minHeap.add(10);
minHeap.add(20);
minHeap.add(17);
minHeap.poll();
List<Integer> heapElements = minHeap.traverse();
System.out.println("Heap elements: " + heapElements.toString());
}
}
最大堆（Max Heap）：任何父节点的值都大于或等于其子节点的值。常用于快速访问最大元素。
最根堆示例
8
/ \
6 5
/ \ / \
4 2 1 3
public class MaxHeap {
/**
* 存储堆元素的数组。
*/
private int[] heap;
/**
* 当前堆中元素的数量。
*/
private int size;
/**
* 堆的最大容量。
*/
private int capacity;
/**
* 构造函数，初始化最大堆。
* @param capacity 堆的初始容量。
*/
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
/**
* 获取父节点的索引。
* @param i 当前节点的索引。
* @return 父节点的索引。
*/
private int getParentIndex(int i) {
return (i - 1) / 2;
}
/**
* 获取左子节点的索引。
* @param i 当前节点的索引。
* @return 左子节点的索引。
*/
private int getLeftChildIndex(int i) {
return 2 * i + 1;
}
/**
* 获取右子节点的索引。
* @param i 当前节点的索引。
* @return 右子节点的索引。
*/
private int getRightChildIndex(int i) {
return 2 * i + 2;
}
/**
* 判断是否有父节点。
* @param i 当前节点的索引。
* @return 如果有父节点返回 true，否则返回 false。
*/
private boolean hasParent(int i) {
return getParentIndex(i) >= 0;
}
/**
* 判断是否有左子节点。
* @param i 当前节点的索引。
* @return 如果有左子节点返回 true，否则返回 false。
*/
private boolean hasLeftChild(int i) {
return getLeftChildIndex(i) < size;
}
/**
* 判断是否有右子节点。
* @param i 当前节点的索引。
* @return 如果有右子节点返回 true，否则返回 false。
*/
private boolean hasRightChild(int i) {
return getRightChildIndex(i) < size;
}
/**
* 交换堆中两个元素的位置。
* @param i 第一个元素的索引。
* @param j 第二个元素的索引。
*/
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
/**
* 上浮操作，用于保持堆的特性。
* 当一个新元素被添加到堆中，我们需要保证这个元素上浮到正确的位置，以维持最大堆的特性。
*/
private void heapUp() {
int index = size - 1;
while (hasParent(index) && heap[getParentIndex(index)] < heap[index]) {
swap(getParentIndex(index), index);
index = getParentIndex(index);
}
}
/**
* 下沉操作，用于在移除堆顶元素后重建堆。
* 当堆顶元素被移除后，我们需要将最后一个元素移到顶部，然后进行下沉操作以维持最大堆的特性。
*/
private void heapDown() {
int index = 0;
while (hasLeftChild(index)) {
int biggerChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && heap[getRightChildIndex(index)] > heap[biggerChildIndex]) {
biggerChildIndex = getRightChildIndex(index);
}
if (heap[index] > heap[biggerChildIndex]) {
break;
} else {
swap(index, biggerChildIndex);
}
index = biggerChildIndex;
}
}
/**
* 向堆中添加新元素。
* @param item 要添加的元素。
*/
public void add(int item) {
if (size == capacity) {
heap = Arrays.copyOf(heap, capacity * 2);
capacity *= 2;
}
heap[size] = item;
size++;
heapUp();
}
/**
* 移除并返回堆顶元素，即最大元素。
* @return 堆顶元素。
*/
public int poll() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int item = heap[0];
heap[0] = heap[size - 1];
size--;
heapDown();
return item;
}
/**
* 返回但不移除堆顶元素。
* @return 堆顶元素。
*/
public int peek() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
return heap[0];
}
/**
* 遍历并返回堆中的所有元素。
* @return 堆中所有元素的列表。
*/
public List<Integer> traverse() {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < size; i++) {
result.add(heap[i]);
}
return result;
}
/**
* 主方法，用于演示最大堆的使用。
*/
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.add(15);
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(17);
maxHeap.poll();
List<Integer> heapElements = maxHeap.traverse();
System.out.println("Heap elements: " + heapElements.toString());
}
}
文章来源:https://blog.csdn.net/weixin_47705408/article/details/135351123
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！