Java堆调整算法详解：向上与向下操作实现

从现在开始，我们要努力学习啦！今天我给大家带来《Java堆的向上调整与向下调整实现方法》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

使用Java构建完整堆需定义包含数组、大小和容量的类，并实现插入、删除、获取堆顶等方法；2. 插入时先将元素放入数组末尾并执行向上调整以恢复堆性质；3. 删除堆顶时用最后一个元素替换堆顶并执行向下调整；4. 获取堆顶直接返回数组首元素；5. 向上调整从插入位置比较父节点直至根节点满足堆性质；6. 向下调整从根节点开始比较子节点并交换最大者直至子树满足堆性质；7. 堆排序通过先构建最大堆再依次将堆顶与末尾元素交换并调整堆完成排序；8. 堆排序时间复杂度为O(n log n)，空间复杂度为O(1)，但不稳定；9. 优先级队列利用堆实现，Java中PriorityQueue默认为最小堆，可通过Comparator实现最大堆；10. 堆广泛应用于任务调度、事件处理、Huffman编码及图算法如Dijkstra和Prim算法中。

堆的向上调整和向下调整是堆排序和优先级队列等数据结构中非常关键的操作。它们用于维护堆的性质，确保堆顶元素始终满足特定条件（例如，最大堆中堆顶是最大值）。

 // 向上调整（Sift Up）：用于在堆尾插入元素后，维护堆的性质
    public static void heapifyUp(int[] arr, int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (arr[index] > arr[parentIndex]) { // 最大堆，如果子节点大于父节点，则交换
                swap(arr, index, parentIndex);
                index = parentIndex;
            } else {
                break; // 满足堆性质，停止调整
            }
        }
    }

    // 向下调整（Sift Down）：用于在堆顶删除元素后，维护堆的性质
    public static void heapifyDown(int[] arr, int index, int heapSize) {
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int largest = index;

            if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largest]) {
                largest = leftChildIndex;
            }

            if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largest]) {
                largest = rightChildIndex;
            }

            if (largest != index) {
                swap(arr, index, largest);
                index = largest;
            } else {
                break; // 满足堆性质，停止调整
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        // 模拟插入元素后的向上调整
        arr[arr.length - 1] = 12; // 假设在堆尾插入12
        heapifyUp(arr, arr.length - 1);
        System.out.println("向上调整后的堆: " + Arrays.toString(arr));

        // 模拟删除堆顶元素后的向下调整
        arr[0] = arr[arr.length - 1];
        int[] newArr = Arrays.copyOf(arr, arr.length - 1); // 移除最后一个元素
        heapifyDown(newArr, 0, newArr.length);
        System.out.println("向下调整后的堆: " + Arrays.toString(newArr));
    }

如何使用Java代码构建一个完整的堆数据结构？

除了向上和向下调整，一个完整的堆数据结构还需要包括插入、删除、获取堆顶元素等操作。同时，需要一个内部数组来存储堆元素，并维护堆的大小。

import java.util.Arrays;

public class Heap {
    private int[] heapArray;
    private int heapSize;
    private int capacity;

    public Heap(int capacity) {
        this.capacity = capacity;
        this.heapArray = new int[capacity];
        this.heapSize = 0;
    }

    // 插入元素
    public void insert(int key) {
        if (heapSize == capacity) {
            resizeHeap();
        }
        heapArray[heapSize] = key;
        heapifyUp(heapArray, heapSize);
        heapSize++;
    }

    // 获取堆顶元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        return heapArray[0];
    }

    // 删除堆顶元素
    public int poll() {
        if (isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        int root = heapArray[0];
        heapArray[0] = heapArray[heapSize - 1];
        heapSize--;
        heapifyDown(heapArray, 0, heapSize);
        return root;
    }

    // 向上调整
    private void heapifyUp(int[] arr, int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (arr[index] > arr[parentIndex]) {
                swap(arr, index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 向下调整
    private void heapifyDown(int[] arr, int index, int heapSize) {
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int largest = index;

            if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largest]) {
                largest = leftChildIndex;
            }

            if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largest]) {
                largest = rightChildIndex;
            }

            if (largest != index) {
                swap(arr, index, largest);
                index = largest;
            } else {
                break;
            }
        }
    }

    // 交换元素
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 扩容
    private void resizeHeap() {
        capacity *= 2;
        heapArray = Arrays.copyOf(heapArray, capacity);
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public static void main(String[] args) {
        Heap maxHeap = new Heap(5);
        maxHeap.insert(4);
        maxHeap.insert(10);
        maxHeap.insert(3);
        maxHeap.insert(5);
        maxHeap.insert(1);

        System.out.println("堆顶元素: " + maxHeap.peek());
        System.out.println("删除堆顶元素: " + maxHeap.poll());
        System.out.println("堆顶元素: " + maxHeap.peek());
    }
}

堆排序算法的Java实现及其性能分析

堆排序是一种基于堆数据结构的排序算法。它的基本思想是首先将待排序的数组构建成一个堆，然后将堆顶元素（最大值或最小值）与堆尾元素交换，缩小堆的范围，并重新调整堆，重复这个过程直到所有元素都排序完成。

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, n);
        }

        // 排序
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(int[] arr, int index, int heapSize) {
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int largest = index;

            if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largest]) {
                largest = leftChildIndex;
            }

            if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largest]) {
                largest = rightChildIndex;
            }

            if (largest != index) {
                swap(arr, index, largest);
                index = largest;
            } else {
                break;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1, 2};
        heapSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}

性能分析：

• 时间复杂度： 堆排序的时间复杂度为O(n log n)，其中n是数组的长度。构建堆的时间复杂度为O(n)，排序过程的时间复杂度为O(n log n)。
• 空间复杂度： 堆排序是一种原地排序算法，只需要常数级别的额外空间，因此空间复杂度为O(1)。
• 稳定性： 堆排序是不稳定的排序算法。

堆排序的优点是其时间复杂度稳定，且空间复杂度低。但由于其不稳定性，在对稳定性有要求的场景下，可能需要考虑其他排序算法。

堆在优先级队列中的应用场景和Java实现

优先级队列是一种特殊的队列，其中每个元素都关联一个优先级。优先级高的元素先出队。堆非常适合实现优先级队列，因为堆可以快速找到最大或最小元素（取决于最大堆还是最小堆）。

import java.util.PriorityQueue;

public class PriorityQueueExample {

    public static void main(String[] args) {
        // 使用PriorityQueue实现最小优先级队列
        PriorityQueue minPriorityQueue = new PriorityQueue<>();

        minPriorityQueue.add(4);
        minPriorityQueue.add(10);
        minPriorityQueue.add(3);
        minPriorityQueue.add(5);
        minPriorityQueue.add(1);

        System.out.println("最小优先级队列: " + minPriorityQueue);
        System.out.println("优先级最高的元素: " + minPriorityQueue.peek());
        System.out.println("删除优先级最高的元素: " + minPriorityQueue.poll());
        System.out.println("优先级最高的元素: " + minPriorityQueue.peek());

        // 使用PriorityQueue实现最大优先级队列 (需要自定义Comparator)
        PriorityQueue maxPriorityQueue = new PriorityQueue<>((a, b) -> b - a);

        maxPriorityQueue.add(4);
        maxPriorityQueue.add(10);
        maxPriorityQueue.add(3);
        maxPriorityQueue.add(5);
        maxPriorityQueue.add(1);

        System.out.println("最大优先级队列: " + maxPriorityQueue);
        System.out.println("优先级最高的元素: " + maxPriorityQueue.peek());
        System.out.println("删除优先级最高的元素: " + maxPriorityQueue.poll());
        System.out.println("优先级最高的元素: " + maxPriorityQueue.peek());
    }
}

应用场景：

• 任务调度： 优先级队列可以用于任务调度，优先级高的任务先执行。
• 事件处理： 在事件驱动的系统中，优先级队列可以用于处理事件，优先级高的事件先处理。
• 数据压缩： Huffman编码是一种常用的数据压缩算法，它使用优先级队列来构建Huffman树。
• 图算法： Dijkstra算法和Prim算法等图算法使用优先级队列来寻找最短路径或最小生成树。

Java的PriorityQueue类底层使用堆实现，提供了高效的优先级队列操作。 可以通过自定义Comparator来实现最大优先级队列。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。