資料結構之Heap (Java)

Heap簡介

　　Heap譯為“堆”，是一種特殊的樹形資料結構，它滿足所有堆的特性：父節點的值大于等于子節點的值(max heap)，或者小于等于子節點的值(min heap)。對于max heap 根節點的值為整個樹最大值，反之亦然，min heap 根節點的值為整個樹最小值。本文采用Java程式設計語言簡單實作min heap。

Java Heap

　　對于大多數應用來說，Java堆 (Java Heap) 是Java虛拟機所管理的記憶體中最大的一塊。Java堆是被所有線程共享的一塊記憶體區域，在虛拟機啟動時建立。此記憶體區域的唯一目的就是存放對象執行個體，幾乎所有的對象執行個體都在這裡配置設定記憶體。根據Java虛拟機規範的規定，Java堆可以處于實體上不連續的記憶體空間中，隻要邏輯上是連續的即可，就像我們的磁盤空間一樣。如果在堆中沒有記憶體完成執行個體配置設定，并且堆也無法再擴充時，将會抛出OutOfMemoryError異常。

結構示意圖

資料結構之Heap (Java)

min heap

資料結構之Heap (Java)

max heap

結構轉換

　　不像其他的樹形結構，例如二叉查找樹，采用連結清單的形式實作，Heap一般用數組實作。這種數組采用自上至下，自左至右的形式從樹中添加元素。圖2-2展示了如何把圖2-1樹形結構(不是Heap資料結構)存儲到數組中。箭頭指向數組中每個元素的直接左孩子和右孩子。

資料結構之Heap (Java)

　　　　　　　　　　　　　　　圖2-1

資料結構之Heap (Java)

　　　　　　　　　　　　　　　　圖2-2

　　僅用一個數組是不足以表示一個堆，程式在運作時的操作可能會超過數組的大小。是以我們需要一個更加動态的資料結構，滿足以下特性：

　　1.我們可以指定數組的初始化大小。

　　2.這種資料結構封裝了自增算法，當程式需要時，能夠增加數組的大小以滿足需求。

　　這會使我們聯想起ArrayList的實作，正是采用這種資料結構。本文就采用了ArrayList的自增算法。

　　因為我們使用數組，我們需要知道如何計算指定節點(index)的父節點、左孩子和右孩子的索引。

　　parent index : (index - 1) / 2

　　left child : 2 * index + 1

　　right child : 2 * index + 2

實作

Insertion

　　為堆設計一個插入算法很簡單，但是我們需要保證每次插入過後，依舊滿足堆的順序。插入算法分為兩步：

　　1.将元素插入到數組中。

　　2.保證數組滿足堆的順序。

　　對于min heap而言，如果插入插入的元素的value小于父節點的value，則需要交換這兩個節點。對于包含新插入節

點的每個子樹，我們都要做上述檢查。時間複雜度為 O (log n)。

　　對于插入的元素為空值，依據需求可以有不同的算法設計，有時可以認為null比任何非空值小，或者比任何非空值大

本文直接禁止插入空值。

　　圖3-1展示了插入值為3，9，12，7和1的元素到min heap的步驟。　　

資料結構之Heap (Java)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖3-1

/**
 * @description insertion
 * @param element
 * @return
 */
public boolean add(E element) {
    if(null == element) 
        return false;
    ensureCapacityInternal(size + 1);
    elementData[size++] = element;
    minHeapify();
    return true;
}

private void minHeapify() {
    int i = size - 1;
    while(i > 0 && compare(elementData[i], elementData[(i-1)/2]) < 0) {
        swap(elementData, i, (i-1)/2);
        i = (i - 1) / 2;
    }
}

Deletion

　　和插入算法類似，删除一個元素過後要保證數組内的元素依舊滿足堆的順序。删除算法分為三步：

　　1.找出待删除元素的索引。

　　2.将堆中最後一個元素的值填到待删除元素位置。

　　3.驗證所有包含被删除元素子樹，確定滿足堆的順序。　

　　圖3-2展示了删除索引為0的元素的過程。

資料結構之Heap (Java)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖3-2

public boolean remove(Object element) {
    int index = indexOf(element);
    
    if(index == -1) {
        return false;
    }
    
    removeInternal(index);
    
    return true;
}

private void removeInternal(int index) {
    elementData[index] = elementData[--size];
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    while(left < size && (compare(elementData[index], elementData[left]) > 0 
            || compare(elementData[index], elementData[right]) > 0)) {
        if(compare(elementData[left], elementData[right]) < 0) {
            swap(elementData, index, left);
            index = left;
        } else {
            swap(elementData, index, right);
            index = right;
        }
        left = 2 * index + 1;
        right = 2 * index + 2;
    }
}

Searching

　　搜尋一個堆，可以順序遍數組。如果待查找元素不在堆中，則需要周遊所有元素，效率較低。

因為我們表示樹的數組是采用自上至下，自左至右的方式從樹中擷取元素，插入到數組中的，是以可以采用

廣度優先周遊的方式(breadth first traversal)。根據min heap的屬性，父節點的值小于等于孩子節點的值。

如果在查找過程中發現待查找元素不滿足條件，可以直接傳回-1，表示沒有此元素。

/**
 * @description index of o 
 * min-heap properties parents < children breadth first  traversal
 * @param o
 * @return
 */
public int indexOf(Object o) {
    int start = 0;
    int node = 1;
    while(start < size) {
        start = node - 1;
        int end = start + node;
        int count = 0;
        while(start < size && start < end) {
            if(start == 0) {
                if(compare(o, elementData[start]) == 0) {
                    return start;
                } else if(compare(o, elementData[start]) < 0) {
                    return -1;
                }
            } else {
                if(compare(o, elementData[start]) == 0) {
                    return start;
                } else if (compare(o, elementData[start]) < 0 &&
                        compare(o, getParent(start)) > 0) {
                    count++;
                } 
            }
            start++;
        }
        if(count == node) {
            return -1;
        } else {
            node = node * 2;
        }
    }  
    return -1;
}

源碼

import java.util.Arrays;
import java.util.Collection;

public class Heap<E extends Comparable<E>> {
    
    private int size; // default 0
    
    private static final int DEFAULT_CAPACITY = 10;
    
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    transient Object[] elementData;
    
    public Heap() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * @description insertion
     * @param element
     * @return
     */
    public boolean add(E element) {
        if(null == element) 
            return false;
        ensureCapacityInternal(size + 1);
        elementData[size++] = element;
        minHeapify();
        return true;
    }
    
    private void minHeapify() {
        int i = size - 1;
        while(i > 0 && compare(elementData[i], elementData[(i-1)/2]) < 0) {
            swap(elementData, i, (i-1)/2);
            i = (i - 1) / 2;
        }
    }
    
    public boolean remove(Object element) {
        int index = indexOf(element);
        
        if(index == -1) {
            return false;
        }
        
        removeInternal(index);
        
        return true;
    }
    
    public E remove(int index) {
        rangeCheck(index);
        E oldVal = elementData(index);
        
        removeInternal(index);
         
        return oldVal;
    }
    
    public E getParent(int index) {
        return elementData(getParentIndex(index));
    }
    
    public E getParent(Object child) {
        return getParent(indexOf(child));
    }
    
    public int getParentIndex(int index) {
        positionCheck(index);
        return (index - 1) / 2;
    }
    
    public E getLeftChild(int index) {
        int leftIndex = getLeftChildIndex(index);
        return (leftIndex == -1) ? null : elementData(leftIndex);
    }
    
    public E getLeftChild(Object o) {
        return getLeftChild(indexOf(o));
    }
    
    public int getLeftChildIndex(int index) {
        rangeCheck(index);
        int leftIndex = 2 * index + 1;
        return (leftIndex >= size) ? -1 : leftIndex;  
    }
    
    public E getRightChild(int index) {
        int rightIndex = getRightChildIndex(index);
        return (rightIndex == -1) ? null : elementData(rightIndex);
    }
    
    public E getRightChild(Object o) {
        return getRightChild(indexOf(o));
    }
    
    public int getRightChildIndex(int index) {
        rangeCheck(index);
        int rightIndex = 2 * index + 2;
        return (rightIndex >= size) ? -1 : rightIndex;
    }
    
    private void removeInternal(int index) {
        elementData[index] = elementData[--size];
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while(left < size && (compare(elementData[index], elementData[left]) > 0 
                || compare(elementData[index], elementData[right]) > 0)) {
            if(compare(elementData[left], elementData[right]) < 0) {
                swap(elementData, index, left);
                index = left;
            } else {
                swap(elementData, index, right);
                index = right;
            }
            left = 2 * index + 1;
            right = 2 * index + 2;
        }
    }
    
    public void traverse(Collection<E> container) {
        for(int i = 0; i < size; i++) {
            container.add(elementData(i));
        }
    }
    
    /**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        if(index >= size) {
            throw new ArrayIndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }
    
    private void positionCheck(int index) {
        if(index <= 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }
    
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
    
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    } 
    
    @SuppressWarnings("unchecked")
    private int compare(Object a, Object b) {
        return ((E)a).compareTo((E)b);
    }
    
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    
    /**
     * @description breadth first traversal
     * @param o
     * @return
     */
    public int indexOf(Object o) {
        int start = 0;
        int node = 1;
        while (start < size) {
            start = node - 1;
            int end = start + node;
            int count = 0;
            while (start < size && start < end) {
                if (start == 0) {
                    if (compare(o, elementData[start]) == 0) {
                        return start;
                    } else if (compare(o, elementData[start]) < 0) {
                        return -1;
                    }
                } else {
                    if (compare(o, elementData[start]) == 0) {
                        return start;
                    } else if (compare(o, elementData[start]) < 0 && compare(o, getParent(start)) > 0) {
                        count++;
                    }
                }
                start++;
            }
            if (count == node) {
                return -1;
            } else {
                node = node * 2;
            }
        }
        return -1;
    }
    
    public void swap(Object[] o, int a, int b) {
        Object t = o[a];
        o[a] = o[b];
        o[b] = t;
    }
    
    public Heap(int initialCapacity) {
        if(initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        }else if(initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }
    
    public void ensureCapacity(int minCapacity) {
        int minExpend = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        if(minCapacity > minExpend) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(minCapacity, DEFAULT_CAPACITY);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        if(minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }
    
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if(newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        if(newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    public int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }

}

Fork me on GitHub: https://github.com/michaelwong95

轉載于:https://www.cnblogs.com/jwongo/p/datastructure-heap.html

資料結構之Heap (Java)

Heap簡介

Java Heap

結構示意圖

結構轉換

實作

Insertion

Deletion

Searching

源碼

繼續閱讀

nginx location中斜線的位置的重要性

nginx 安裝錯誤資訊解決

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Ambari介紹和架構原理

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method