实现堆

Question

我正在尝试实现一个堆数据结构，我编写了构建最大堆的maxHeapify方法，并在我的insert方法中使用它，我在插入方法的末尾插入，然后重新排列堆以保持最大堆。但它似乎不起作用，任何帮助都将不胜感激。

    public class Heap { // a class to implement a heap
        private int[] data; // the heap array
        private static final int FRONT = 1;
        private int maxSize = 0;
        private int currentSize; // the current size of the data in the array

    public Heap(int maxSize) {
        this.currentSize = 1;
        this.maxSize = maxSize;
        data = new int[maxSize + 1];
    }

    public int[] getData() {
        return data;
    }

    public void setData(int[] data) {
        this.data = data;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public void setCurrentSize(int currentSize) {
        this.currentSize = currentSize;
    }

    @SuppressWarnings("unused")
    private int parent(int index) {// the index of the parent
        return index / 2;
    }

    private int left(int index) { // the index of the left child
        return (2 * index);
    }

    private int right(int index) { // the index of the right child
        return (2 * index) + 1;
    }

    private void swap(int i, int j) { // to swap two elements
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    private void maxHeapify(int i) { // to build a max heap
        int left = left(i); // a method to return the index of the left child
        int right = right(i);// a method to return the index of the right child
        int largest = i;
        int x = currentSize;
        if (left <= currentSize && data[left] > data[i]) {
            largest = left;
        }
        if (right <= currentSize && data[right] > data[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = data[i];
            data[i] = data[largest];
            data[largest] = temp;
            maxHeapify(largest);
        }
    }

    public void maxHeap() {
        for (int i = currentSize / 2; i >= 1; i--) {
            maxHeapify(i);
        }
    }

    public void insert(int newData) { // insert to the heap
        data[currentSize] = newData;
        currentSize++;
        maxHeapify(FRONT);


    }

    public int deleteMax() { // delete max from the heap
        int maxValue = data[FRONT];
        data[FRONT] = data[data.length - 1];
        maxHeapify(FRONT);
        currentSize--;
        return maxValue;

    }

    public void sort() {// heap sort
        maxHeap();
        for (int i = maxSize; i > 1; i--) {
            swap(FRONT, maxSize);
            maxSize--;
            maxHeapify(FRONT);
        }
    }

    public void clear() {
        maxSize = 0;
    }

    public boolean isEmpty() {

        return maxSize == 0;
    }

    public boolean isFull() {
        return currentSize == data.length;
    }

    public void printHeap() {// prints the heap
        for (int i = 1; i <= maxSize / 2; i++) {
            System.out.print(
                    " PARENT : " + data[i] + " LEFT CHILD : " + data[2 * i] + " RIGHT CHILD :" + data[2 * i + 1]);
            System.out.println();
        }
    }
}

Answer 1

当你在堆的根上添加新的数字时，你的函数maxHeapify就会起作用。我的意思是说，在maxHeapify中，你是从根到子。但在插入过程中，您会将元素插入到最后。你必须从下往上移动。

maxHeapify :从根到下。

在将元素插入到数据数组之后，您必须从子级到父级向上检查，这与maxHeapify完全相反。

Answer 2

这应该是可行的：

    /**
     * Parent.
     *
     * @param pos the pos
     * @return the int
     */
    private int parent(int pos)
    {
        return pos / 2;
    }

    /**
     * Left.
     *
     * @param pos the pos
     * @return the int
     */
    private int left(int pos)
    {
        return (2 * pos);
    }

    /**
     * Right.
     *
     * @param pos the pos
     * @return the int
     */
    private int right(int pos)
    {
        return (2 * pos) + 1;
    }

    /**
     * Checks if is leaf.
     *
     * @param pos the pos
     * @return true, if is leaf
     */
    private boolean isLeaf(int pos)
    {
        if (pos >=  (size / 2)  &&  pos <= size)
        {
            return true;
        }
        return false;
    }

    /**
     * Swap.
     *
     * @param fpos the fpos
     * @param spos the spos
     */
    private void swap(int fpos,int spos)
    {
        int tmp;
        tmp = data[fpos];
        data[fpos] = data[spos];
        data[spos] = tmp;
    }

    /**
     * Max heapify.
     *
     * @param pos the pos
     */
    private void maxHeapify(int pos)
    {
        if (!isLeaf(pos))
        { 
            if ( data[pos] < data[left(pos)]  || data[pos] < data[right(pos)])
            {
                if (data[left(pos)] > data[right(pos)])
                {
                    swap(pos, left(pos));
                    maxHeapify(left(pos));
                }else
                {
                    swap(pos, right(pos));
                    maxHeapify(right(pos));
                }
            }
        }
    }

    /**
     * Insert.
     *
     * @param newElement the element
     */
    public void insert(int newElement)
    {
        data[++size] = newElement;
        int current = size;

        while(data[current] > data[parent(current)])
        {
            swap(current,parent(current));
            current = parent(current);
        }   
    }

Answer 3

在最后一个位置添加新元素后，您需要上移。举个例子。

public void insert(int value) {
            if (heapSize == data.length)
                  throw new HeapException( storage is overflow");
            else {
                  heapSize++;
                  data[heapSize - 1] = value;
                  siftUp(heapSize - 1);
            }
      } 
 private void siftUp(int nodeIndex) {
 //code to hepify.
}