堆：有兩種，一種是大根堆，另一種是小根堆。大根堆的意思是在跟的位置那個數是最大的。同理，小根堆的根元素是最小的。 堆是一個滿的二叉樹，除了最后一個節點可能不是滿的。所以用數組去數組去實現它。一個節點的index為i,則這個節點的兩個子節點的下標應該為2*i+1和2* i+2;父結點那就是(i-1)/2;
下面是大根堆代碼的實現：
public class MyHeap<E extends Comparable<E>> { PRivate Object[] array; private int maxSize; private int currentSize; public MyHeap(int max){ maxSize = max; array = new Object[max]; currentSize = 0; } public boolean isEmpty(){ return currentSize == 0; } /** * 插入節點 * @param e */ public boolean insert(E e){ if(currentSize == maxSize) return false; array[currentSize] = e; checkUp(currentSize++); return true; } /** * 向上移動函數 * @param i */ private void checkUp(int i) { // TODO Auto-generated method stub int parent = (i-1)/2; E object = (E) array[i]; /** * 說一下解決思路：插入的節點是在數組最后一個位置，需要拿到這個節點的父結點，也就是parent的位置 * 然后就跟父結點比較，如果比父結點大的話那就需要去交換，這里可能會忘了數組索引是要大于等于0的 * */ while (i>0&&object.compareTo((E) array[parent])>0) { array[i] = array[parent]; i = parent ; parent = (parent-1)/2; } array[i] = object; } public E remove(){ E e = (E) array[0]; array[0] = array[--currentSize]; checkDown(0); return e; } /** * 使小的節點向下走 * @param i */ private void checkDown(int i) { int laChrid; E e = (E) array[i]; while(i<currentSize/2){ int left = 2*i+1; int right = left +1; E e2 = (E) array[left]; if(right<currentSize&&e2.compareTo((E)array[right])<0) laChrid = right; else { laChrid = left; } if(e.compareTo((E)array[laChrid])>=0) break; array[i] = array[laChrid]; i = laChrid; } array[i] = e; }}新聞熱點
疑難解答
