江苏龙网

  1. 主页 > 生活百科 > >

堆和二叉堆的实现和特性( 二 )

二叉堆

  • 第二步：依次向上调整整个堆的结构，就叫 HeapifyUp

    • 堆和二叉堆的实现和特性

    文章插图
     
    85 按照上面讲的先插入到堆的尾部，也就是一维数组的尾部，一维数组的尾部的话就上图的位置，因为这是一个完全二叉树，所以它的尾部就是50后面这个结点 。插进来之后这个时候就破坏了堆，它的每一个结点都要大于它的儿子的这种属性了，接下来要做的事情就是要把 85 依次地向上浮动，怎么浮动？就是 85 大于它的父亲结点，那么就和父亲结点进行交换，直到走到根如果大于根的话，就和根也进行交换 。
    堆和二叉堆的实现和特性

    文章插图
     
    85 再继续往前走之后，它要和 80 再进行比较，同理可得：也就是说这个结点每次和它的父亲比，如果它大于它的父亲的话就交换，直到它不再大于它的父亲 。
    堆和二叉堆的实现和特性

    文章插图
     
    Delete Max 删除堆顶操作
    1. 将堆尾元素替换到顶部（即堆顶被替代删除掉）
    2. 依次从根部向下调整整个堆的结构（一直到堆尾即可） HeapifyDown
    例子：90 从二叉堆中删除
    堆和二叉堆的实现和特性

    文章插图
     
    堆的实现代码模版JAVA 版本// Javaimport java.util.Arrays;import java.util.NoSuchElementException;public class BinaryHeap {    private static final int d = 2;    private int[] heap;    private int heapSize;    /**     * This will initialize our heap with default size.     */    public BinaryHeap(int capacity) {        heapSize = 0;        heap = new int[capacity + 1];        Arrays.fill(heap, -1);    }    public boolean isEmpty() {        return heapSize == 0;    }    public boolean isFull() {        return heapSize == heap.length;    }    private int parent(int i) {        return (i - 1) / d;    }    private int kthChild(int i, int k) {        return d * i + k;    }    /**     * Inserts new element in to heap     * Complexity: O(log N)     * As worst case scenario, we need to traverse till the root     */    public void insert(int x) {        if (isFull()) {            throw new NoSuchElementException("Heap is full, No space to insert new element");        }        heap[heapSize] = x;        heapSize ++;        heapifyUp(heapSize - 1);    }    /**     * Deletes element at index x     * Complexity: O(log N)     */    public int delete(int x) {        if (isEmpty()) {            throw new NoSuchElementException("Heap is empty, No element to delete");        }        int maxElement = heap[x];        heap[x] = heap[heapSize - 1];        heapSize--;        heapifyDown(x);        return maxElement;    }    /**     * Maintains the heap property while inserting an element.     */    private void heapifyUp(int i) {        int insertValue = heap[i];        while (i > 0 && insertValue > heap[parent(i)]) {            heap[i] = heap[parent(i)];            i = parent(i);        }        heap[i] = insertValue;    }    /**     * Maintains the heap property while deleting an element.     */    private void heapifyDown(int i) {        int child;        int temp = heap[i];        while (kthChild(i, 1) < heapSize) {            child = maxChild(i);            if (temp >= heap[child]) {                break;            }            heap[i] = heap[child];            i = child;        }        heap[i] = temp;    }    private int maxChild(int i) {        int leftChild = kthChild(i, 1);        int rightChild = kthChild(i, 2);        return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;    }    /**     * Prints all elements of the heap     */    public void printHeap() {        System.out.print("nHeap = ");        for (int i = 0; i < heapSize; i++)            System.out.print(heap[i] + " ");        System.out.println();    }    /**     * This method returns the max element of the heap.     * complexity: O(1)     */    public int findMax() {        if (isEmpty())            throw new NoSuchElementException("Heap is empty.");        return heap[0];    }    public static void main(String[] args) {        BinaryHeap maxHeap = new BinaryHeap(10);        maxHeap.insert(10);        maxHeap.insert(4);        maxHeap.insert(9);        maxHeap.insert(1);        maxHeap.insert(7);        maxHeap.insert(5);        maxHeap.insert(3);        maxHeap.printHeap();        maxHeap.delete(5);        maxHeap.printHeap();        maxHeap.delete(2);        maxHeap.printHeap();    }}


    推荐阅读


    上一篇：没有了

    下一篇：Linux查看硬件信息超强命令sar，以及可视化工具ksar