堆：有两种，一种是大根堆，另一种是小根堆。大根堆的意思是在跟的位置那个数是最大的。同理，小根堆的根元素是最小的。 堆是一个满的二叉树，除了最后一个节点可能不是满的。所以用数组去数组去实现它。一个节点的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; }}新闻热点
疑难解答
