从头开始实现堆排序

Question

import java.util.Arrays;

import javax.management.RuntimeErrorException;

public class MyHeap {

public static void main(String args) {
        MyHeap minHeap = new MyHeap(10, true);
        minHeap.insert(70);
        minHeap.insert(20);
        minHeap.insert(90);
        minHeap.insert(60);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.insert(50);
        minHeap.insert(30);
        minHeap.insert(80);
        minHeap.insert(100);

        System.out.println("Min Heap: " + Arrays.toString(minHeap.heap));
    
        MyHeap maxHeap = new MyHeap(10, false);
        maxHeap.insert(70);
        maxHeap.insert(20);
        maxHeap.insert(90);
        maxHeap.insert(60);
        maxHeap.insert(40);
        maxHeap.insert(10);
        maxHeap.insert(50);
        maxHeap.insert(30);
        maxHeap.insert(80);
        maxHeap.insert(100);
    
        System.out.println("Max Heap: " + Arrays.toString(maxHeap.heap));
    }
    
    private int[] heap;
    private int size = 0;
    private int capacity;
    private boolean reverse;// true if min heap
    
    public MyHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        // max heap by default
        this.reverse = false;
    }
    
    public MyHeap(int capacity, boolean reverse) {
        this.capacity = capacity;
        heap = new int[capacity];
        this.reverse = reverse;
    }
    
    private int compare(int a, int b) {
        if (reverse)
            return b - a;
        return a - b;
    }
    
    public void insert(int key) {
        if (isFull()) {
            throw new IndexOutOfBoundsException("Out of given capacity");
        }
        heap[size] = key;
        swim(size++);
    }
    
    // private void rightshift(int parent, int position) {
    // for (int i = position; i > parent; i--) {
    // if (compare(heap[i], heap[i - 1]) > 0)
    // swap(i, i - 1);
    // }
    // }
    
    private void swim(int position) {
        int parent = (position) / 2;
        if (position > 0 && compare(heap[parent], heap[position]) < 0) {
            swap(parent, position);
            // rightshift(parent, position);
            swim(parent);
        }
    }
    
    private void sink(int position) {
        int left = position * 2 + 1;
        int right = position * 2 + 2;
        int largest = position;
        if (left < size && compare(heap[position], heap[left]) < 0) {
            largest = left;
        }
        if (right < size && compare(heap[position], heap[right]) < 0) {
            largest = right;
        }
        if (largest != position) {
            swap(largest, position);
            sink(largest);
        }
    
    }
    
    public int getMin() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data available");
        }
        if (reverse) {
            return heap[size - 1];
        }
        return heap[0];
    }
    
    public int getMax() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data available");
        }
        if (reverse) {
            return heap[0];
        }
        return heap[size - 1];
    }
    
    public void delTop() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data Available to delete");
        }
        swap(0, size - 1);
        size--;
        sink(0);
    }
    
    public void delMin() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data Available to delete");
        }
        if (reverse) {
            throw new RuntimeErrorException(null, "You Initialized a Min heap");
        }
        swap(getMin(), 0);
        size--;
        sink(0);
    }
    
    public void delMax() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data Available to delete");
        }
        if (!reverse) {
            throw new RuntimeErrorException(null, "You Initialized a Max heap");
        }
        swap(getMax(), 0);
        size--;
        sink(0);
    }
    
    public int size() {
        return size - 1;
    }
    
    public boolean isFull() {
        return size - 1 == capacity;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    
    @Override
    public String toString() {
        int[] items = Arrays.copyOf(heap, size);
        return Arrays.toString(items);
    }

}

输出：

最小堆：10, 20, 40, 30, 80, 60, 70, 50, 90, 100

最大堆：100、90、80、60、70、10、50、30、20、40

问题描述：

我正在努力在 Java 中实现最小堆和最大堆，但我在正确排序数组时遇到了问题。让我通过一个例子来解释这个问题：

假设我们有一个数组 arr 初始化如下：{0, 0, 0}（最大堆）。

我们插入 70，arr 就变成了 {70, 0, 0}。将不会进行进一步的更改。 我们插入 50，arr 就变成了 {70, 50, 0}。将不会进行进一步的更改。 我们插入 80，arr 就变成了 {70, 50, 80}。这里，80 大于它的父级 (70)，所以我们交换它们。交换后，arr 变为 {80, 50, 70}。 现在，数组仍然没有正确排序。我尝试通过引入 rightshift 函数来解决这个问题，但它没有按预期工作。

我尝试过的：

我已经实现了最小堆和最大堆的基本结构，但我认为问题主要与游泳、下沉和右移函数有关。

我对代码进行了修改，包括调整compare函数以及修改swim和sink函数。然而，数组仍然没有按预期排序。

问题：

我需要帮助修复接收器、游泳和右移函数或任何其他必要的更改，以确保数组针对最小堆和最大堆实现正确排序。您能否检查我的代码并提供有关需要更改哪些内容才能实现此目标的指导？

Answer 1

现在，数组仍然没有正确排序。

堆不是排序的数组，堆排序也不是仅仅构建堆的问题。

这也意味着您不能同时拥有

getMin

和

getMax

功能。您只能获取堆的“顶部”作为可靠值。数组中的最后一个值不保证是另一个极端。出于同样的原因，您不能同时拥有

delMin

和

delMax

函数，只能拥有

delTop

函数，如下所示：

    public void delTop() {
        if (isEmpty()) {
            throw new IllegalStateException("No Data Available to delete");
        }
        swap(0, --size);
        sink(0);
    }

堆排序包括构建一个堆，然后重复地从堆中删除顶部以减小大小，并将提取的值放入已排序的分区中（在末尾）。

错误

除了上面的注释之外，

sink

函数的这一部分还有一个错误：

        if (left < size && compare(heap[position], heap[left]) < 0) {
            largest = left;
        }
        if (right < size && compare(heap[position], heap[right]) < 0) {
            largest = right;
        }

第二个

if

条件将

position

处的条目与

right

处的条目进行比较，但它应该比较

largest

处的条目。所以正确的是：

        if (left < size && compare(heap[position], heap[left]) < 0) {
            largest = left;
        }
        if (right < size && compare(heap[largest], heap[right]) < 0) {
            largest = right;
        }

函数

size()

和

isFull()

在使用

size - 1

时也存在问题，而它们应该使用

size

来代替。这是对两个函数的更正：

    public int size() {
        return size;
    }
    
    public boolean isFull() {
        return size == capacity;
    }

实现堆排序

要实现堆排序，你可以添加这个方法：

    public void sort() {
        // HeapSort algorithm:
        int origSize = size;
        while (size > 1) {
            delTop();
        }
        size = origSize;
        // Reverse, so it also is in line with heap property
        for (int i = 0, j = size - 1; i < j; i++, j--) {
            swap(i, j);
        }            
    }

在主函数中调用这个

sort

方法：

    public static void main(String[] args) {
        MyHeap minHeap = new MyHeap(10, true);
        minHeap.insert(70);
        minHeap.insert(20);
        minHeap.insert(90);
        minHeap.insert(60);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.insert(50);
        minHeap.insert(30);
        minHeap.insert(80);
        minHeap.insert(100);
        minHeap.sort();
        System.out.println("Min Heap: " + minHeap);
    
        MyHeap maxHeap = new MyHeap(10, false);
        maxHeap.insert(70);
        maxHeap.insert(20);
        maxHeap.insert(90);
        maxHeap.insert(60);
        maxHeap.insert(40);
        maxHeap.insert(10);
        maxHeap.insert(50);
        maxHeap.insert(30);
        maxHeap.insert(80);
        maxHeap.insert(100);
        minHeap.sort();
        System.out.println("Max Heap: " + maxHeap);
    }

现在它将按排序顺序打印出值。