使用 minHeapify() 对数组进行排序，并使用 extractMin() 到 return 元素

Question

我正在使用 minHeapify 结构从数组中提取数字，并使用此方法 "minHeapify()" 对我的数组进行排序，并使用 extractMin() 到 return 具有最低值的元素。

它总是 return 第一个元素在前，并且在计算负数时遇到问题。这是我的代码，

    public class PQHeap implements PQ {

    Element[] eList;
    int size;

    public PQHeap(int maxElms){
        eList= new Element[maxElms];
    }

    @Override
    public Element extractMin() {
        size = heapSize(eList);
        if (size <= 0) {
            System.out.println("Empty Array");
            return null;
        }
        Element min = eList[0];
        eList[0] = eList[size -1];
        // sets the last index in the array to null
        eList[size -1]= null;
        size--;
        minHeapify(eList, 0);
        return min;
    }

    public void minHeapify(Element[] array, int num){
        int l = left(num);
        int r = right(num);
        int smallest = num;
        if (l < size && array[l].key < array[smallest].key){
            smallest = l;
        }
        if (r < size && array[r].key < array[smallest].key){
            smallest = r;
        }
        if (smallest != num){
            swap(array, num, smallest);
            minHeapify(array, smallest);
        }
    }

    public void swap(Element[] array,int parent, int smallest){
        Element tmp= array[parent];
        array[parent] = array[smallest];
        array[smallest] = tmp;
    }

    public int heapSize(Element[] array){
        size = 0;
        for (int i = 0; i <array.length; i++) {
            if(array[i] != null){
                size++;
            }
        }
        return size;
    }

    @Override
    public void insert(Element e) {
        int i = 0;
        for (int j = 0; j <eList.length; j++) {
            if(eList[i]== null){
                eList[i] = e;
                break;
            }else{
                i++;
            }
        }
    }

    public int left(int i){
        return 2 * i+1;
    }

    public int right(int i){
        return 2 * i + 2;
    }
}

Element 数组是必须的，所以没有评论说我应该使用数组列表。

当我运行代码是这样的结果：

3、
0,
1、
1、
1、
2、
-117,
3、
5、
100

这是测试class:

System.out.println();
System.out.println("Creating a PQHeap with room for 10 elements");
System.out.println();
    PQ pq = new PQHeap(10);

System.out.println("Inserting elements with keys");
System.out.println("  3, 5, 0, 100, -117, 1, 1, 1, 2, 3");
System.out.println("(and corresponding Integers as data)");
System.out.println();

pq.insert(new Element(3,new Integer(3)));
pq.insert(new Element(5,new Integer(5)));
pq.insert(new Element(0,new Integer(0)));
pq.insert(new Element(100,new Integer(100)));
pq.insert(new Element(-117,new Integer(-117)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(2,new Integer(2)));
pq.insert(new Element(3,new Integer(3)));

System.out.println("Doing 10 extractMins (showing keys and data)");
System.out.println();
Element e;
for (int i=0; i<10; i++){
    e = pq.extractMin();
    System.out.println(e.key + " " + e.data);

Answer 1

我解决了这个问题，不知道我是应该删除 post 还是顺其自然，但这是解决方案。 insert 方法没有遵循 minHeap 结构：

public void insert(Element e) {
    size = heapSize(eList);
    eList[size] = e;
    decreaseKey(eList, size, e.key);
}

public void decreaseKey(Element[] array, int i, int key){
    array[i].key = key;
    while (i > 0 && array[parent(i)].key > array[i].key){
        swap(array,i,parent(i));
        i = parent(i);
    }
}

使用 minHeapify() 对数组进行排序，并使用 extractMin() 到 return 元素

Using minHeapify() to sort array, and extractMin() to return element

java

arrays

sorting

heap