java - 理解 minheap 和 heapSort 方法

Question

我有这两个类，我正在询问 heapSort() 方法。如何在Test calss 中实现它，另外，你能检查一下我的add() 方法和我的smallestChild() 方法吗？

对于 heapSort() 方法，该方法应该对数组进行升序排序算法是遍历数组并将所有数字添加到数组中，然后删除所有数字并将它们放入回阵!!老实说，这个算法让我很困惑，我不知道该怎么做？ heapSort() 需要辅助方法吗？或者如何？

这是第一类 MinHeap

import java.util.NoSuchElementException;
public class MinHeap {
    private int[] heap;   // The heap.
    private int size; // the next index
    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

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

    public void add(int n) {
        if (size < heap.length) {
            size++;
            n = heap[size-1];
            int p = (size -1)/2;
            while(n != 0 && n < heap[p]) {
                swap(size, p);
                size = p;
                p=(size-1)/2;
            }
            size++; 
        } else {
            throw new HeapFullException();
        }
    }

    private int smallestChild(int current) {
        if(size < heap.length) {
            int left = current *2+2;
            int right = current * 2 +1;
            if(heap[left]>heap[right]) {
                return left;
            } else if(heap[right]>heap[left]) {
                return right;
            } else {
                return left;
            }
        } else {
            return -1;
        }       
    }

    public int remove() {
        if (size == 0) {
            // if size has no element to remove throw exception
            throw new NoSuchElementException();
        } else {
            // hold the minimum element
            int minElement = heap[0];
            // set the minimum index to the highest index and decrement the size
            heap[0] = heap[size-1];
            size--;
            int p = 0;
               while(heap[p] > heap[smallestChild(p)]) {
                int c = smallestChild(p);
                swap(p, c);
                p = c;
            }
            return minElement;
        }
    }

    public String toString() {
        String s = "";
        for(int i=0; i<size; i++) {
            s += i + ": " + heap[i] + "\n";
        }
        return s;
    }

    public int[] toArray() {
        int[] a = new int[size];
        for(int i=0; i<size; i++) {
            a[i] = heap[i];
        }
        return a;
    }

    private void swap(int x, int y) {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    class HeapFullException extends RuntimeException {
        public static final long serialVersionUID = 8320632366082135L;
    }
}

我应该编写sortHeap() 方法的Test 类是:

import java.util.Random;
public class Test {

    private static Random rand = new Random();

    public static void main(String[] args) {
    testMinHeap();
    }


    public static void testMinHeap(){
        int[] a = initRandom();
        MinHeap h = new MinHeap(a.length);
        for(int i=0; i<a.length; i++) {
            h.add(a[i]);
        }
        print(a);
        System.out.println("Smallest: " + h.remove());
        int[] b = h.toArray();
        print(b);
    }

    private static int[] initRandom() {
        int[] a = new int[rand.nextInt(40)];
        for(int i=0; i<a.length; i++) {
            a[i] = rand.nextInt(100);
        }
        return a;
    }


    private static void print(int[] a) {
        for(int i=0; i<a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

如何扭曲 sortHeap()？ 请帮助我理解它并为我的考试做好准备 谢谢

Answer 1

您的add 方法不会向堆中添加任何内容；没有将 n 的值放入数组的代码。并且应该通过堆筛选东西的代码是不正确的。 add 的正确版本应该是:

public void add(int n) {
    if (size >= heap.length) {
        throw new HeapFullException();
    }

    // place the item in the heap
    int pos = size;
    heap[pos] = n;
    size++;

    // move the item into position
    int parent = (pos-1)/2;
    while (pos > 0 && heap[parent] > heap[pos]) {
        swap(parent, pos);
        pos = parent;
        parent = (pos-1)/2;
    }
}

您的 smallestChild 方法有几个错误。

private int smallestChild(int current) {
    if(size < heap.length) {
        int left = current *2+2;
        int right = current * 2 +1;
        if(heap[left]>heap[right]) {
            return left;
        } else if(heap[right]>heap[left]) {
            return right;
        } else {
            return left;
        }
    } else {
        return -1;
    }       
}

首先，您将左右子索引颠倒过来。左 child 应该是(current * 2) + 1)，右 child 是left +1。

其次，你无条件地检查 child ，即使这样做会索引堆的末尾。在检查哪个子节点较小之前，您需要确保 current 节点确实有子节点。像这样的事情会做到这一点:

private int smallestChild(int current) {
    int left = current*2+1;
    if (left >= size) {
        return current;
    }
    int smallest = left;
    int right = left+1;
    if (right < size && heap[right] < heap[left]) {
        smallest = right;
    }
    return smallest;
}

对于您的 sortHeap 方法，我认为您需要如下内容:

public static void testMinHeap(){
    int[] a = initRandom();
    MinHeap h = new MinHeap(a.length);
    for(int i=0; i<a.length; i++) {
        h.add(a[i]);
    }

    // now remove things in order and add them back to the array
    int ix = 0;
    while (!h.isEmpty) {
      a[ix] = h.remove();
      ix++;
    }

    print(a);
}