理解小根堆和堆排序方法

Question

我有这两个类，我想问关于heapSort()方法的实现，如何在Test类中进行实现？同时，你能否检查我的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;
    }
}

我应该在Test类中编写sortHeap()方法:

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()？请帮助我理解并为我的考试做好准备。谢谢。

- 3noo6

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;
    }       
}

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

其次，您无条件地检查孩子，即使这样做会超出堆的范围。在检查哪个子节点更小之前，您需要确保当前节点实际上有子节点。像这样的代码可以解决问题：

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);
}

- Jim Mischel

---

如果我的回答解决了你的问题，你可以考虑将其标记为被接受的答案。 - Jim Mischel