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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。