网站设计工资一般多少,便宜网站建设怎么样,wordpress怎么获取数据库,网站 不备案堆一点疑惑#xff0c;堆排序是就地排序#xff0c;所以空间复杂度是 O(1)。但是#xff0c;比如我有一个数组#xff0c;建立一个最小堆#xff0c;然后每次取出最小堆的顶点。建立最小堆需要额外空间#xff1f;不深究了#xff0c;归并排序需要额外空间。堆是完全二叉…堆一点疑惑堆排序是就地排序所以空间复杂度是 O(1)。但是比如我有一个数组建立一个最小堆然后每次取出最小堆的顶点。建立最小堆需要额外空间不深究了归并排序需要额外空间。堆是完全二叉树所以可以用数组表示。普通的二叉树需要用链表表示。完全二叉树不等于满二叉树。下图是一个完全二叉树。我们数组下标从0开始。我们可以得到父节点和子节点之前的坐标公式。leftChild 2*parent1;rightChild 2*parent 2;parent (child-1)/2;//child 为 leftChild 或 rightChild插入堆从书上截取的图片注意书上描述的是最大堆我们代码实现的是最小堆。插入堆后保存父节点子节点的性质。代码算法怎么实现呢我们需要保持最大堆的性质插入元素后必然需要移动数组。下面的方法是先把元素插到数组的末尾然后比较该元素和父亲元素判断是否需要交换。重复上述步骤知道遍历完成或者堆已经是最大堆了。代码/** * 增加一个新元素步骤是 1. 先把元素插入到 list 的末尾 2. 比较末尾元素和它的父元素若小于交换两者 3. * 重复上述步骤直到到顶点位置或者子元素大于父元素 4. 不一定要遍历堆所有的元素达到堆的性质后会提前结束 * * param array */public void add(E array) {data.add(array);int child data.size() - 1;int parent (child - 1) / 2;// 判断是否到达顶点while (child 0) {// 父元素大于子元素交换保持父是小的if (data.get(parent).compareTo(array) 0) {data.set(child, data.get(parent));data.set(parent, array);child parent;parent (child - 1) / 2;} else {// 已经是最小堆了无需再比较break;}}}上面使用的是插入的方法充分利用原有最大堆的性质。思路很棒删除顶点元素删除元素我自己想的时候也想不到好方法。看书上的才明白也是利用交换的思路。删除顶点元素然后将最后一个元素移动到顶点处。再从上往下遍历判断顶点元素和它子节点是否满足堆的性质不满足则交换。重复上述步骤知道遍历完成或者堆已经是最大堆。Note 删除和插入元素不一定需要遍历二叉树的所有层当已经满足最大堆的性质时候就可以结束。代码/** * 删除顶点处的元素步骤是 1. 把末尾的元素复制到顶点处 2. 然后比较此时顶点的值和左右子树保持最小堆的性质 3. * 交换顶点和左右子树较小的值 4. 重复上述步骤直到已经成了最小堆或者遍历完 5. 注意可能存在左子树存在右子树不存在情况 6. * 不一定要遍历堆所有的元素达到堆的性质后会提前结束 * * return 返回被删除的元素 */public E removeTop() {if (data.isEmpty())return null;E removed data.get(0);// 因为一直交换的是最后的元素这儿将其保存E last data.get(data.size() - 1);data.set(0, last);data.remove(data.size() - 1);int parent 0;int leftChild parent * 2 1;int rightChild parent * 2 2;while (leftChild data.size() - 1) {int minIndex leftChild;// 右子树存在判断左右子树哪个小保存坐标// 如果不存在那么使用左子树的坐标// 保存较小元素的坐标可以省去考虑左右子树都存在只有左存在的情况if (rightChild data.size() - 1) {if (data.get(rightChild).compareTo(data.get(leftChild)) 0) {minIndex rightChild;}}if (data.get(minIndex).compareTo(last) 0) {data.set(parent, data.get(minIndex));data.set(minIndex, last);parent minIndex;leftChild parent * 2 1;rightChild parent * 2 2;} else {break; // 已经达到了最小堆的性质}}return removed;}注意代码需要考虑左右子树都存在、只有左子树存在的情景。(只有右子树存在是不可能的)。 那么parent需要和left还是right交换呢我本来是用了一大堆if判断。看书上的很简洁先设置minIndex leftChild; (因为左子树是肯定存在的)然后如果右子树存在的情况下 比较左子树和右子树。如果右子树小minIndex rightChild; 否则minIndex不变。然后就可以比较minIndex 和 parent了。而我以前的方法是 先对左右子树的情况比较。找出较小的树然后和parent比较。 再考虑左子树的情况比较左子树和parent。这个方法就很冗余。利用堆进行排序先将原来的数据入堆然后依次取出顶点元素。注意如果是最大堆得到的降序。如果是最小堆得到的是升序。时间复杂度堆是有二叉树实现的对于n个元素建立二叉树的话数的深度是log(n)。add方法会追踪顶点到最下边叶子节点的路径这个路径的长度就是树的深度log(n)。对于建立一个二叉树添加一个元素最多需要log(n)步。所以所以元素添加需要nlog(n)步。注意如果原来数据是升序的对于建立一个最小堆是最好情景对于建立一个最大堆时间是最差情景。进行对排序也需要调用n次remove方法每次remove方法最多需要log(n)步骤。需要的总时间的nlog(n)。全部代码/** * 最小堆和堆排序, 最小堆顶点的元素是最小值 根据《Java 语言程序设计 进阶篇》 p83 改写 书上是最大堆. 堆排序 * 将元素都存入最小堆中从最小堆里面每次取出顶点元素 * * author tomchen * * param */public class MinHeap {// 测试程序public static void main(String[] args) {Random r new Random(System.currentTimeMillis());// 测试10次for (int t 0; t 10; t) {MinHeap heap new MinHeap();int mSize r.nextInt(15);Integer[] original new Integer[mSize];// 堆的长度和元素都是随机for (int i 0; i mSize; i) {original[i] r.nextInt(100);}//copy 数组调用标准库的方法Integer[] copy Arrays.copyOf(original, mSize);Arrays.sort(copy);//这儿输出 original 还是乱序的证明 copy 的排序并无影响System.out.println(original data: Arrays.toString(original));System.out.println(other sorted data: Arrays.toString(copy));// 调用 heap 排序heapSort(original);System.out.println(sorted data: Arrays.toString(original));System.out.println(two sort eqyal : Arrays.equals(copy,original));System.out.println(-----------------------------------------);}}public static void heapSort(E[] array) {MinHeap heap new MinHeap();for (int i 0; i array.length; i) {heap.add(array[i]);}System.out.println(Debug: heap is heap);for (int i 0; i array.length; i) {array[i] heap.removeTop();}}private ArrayList data new ArrayList();public MinHeap() {}/** * 增加一个新元素步骤是 1. 先把元素插入到 list 的末尾 2. 比较末尾元素和它的父元素若小于交换两者 3. * 重复上述步骤直到到顶点位置或者子元素大于父元素 4. 不一定要遍历堆所有的元素达到堆的性质后会提前结束 * * param array */public void add(E array) {data.add(array);int child data.size() - 1;int parent (child - 1) / 2;// 判断是否到达顶点while (child 0) {// 父元素大于子元素交换保持父是小的if (data.get(parent).compareTo(array) 0) {data.set(child, data.get(parent));data.set(parent, array);child parent;parent (child - 1) / 2;} else {// 已经是最小堆了无需再比较break;}}}/** * 删除顶点处的元素步骤是 1. 把末尾的元素复制到顶点处 2. 然后比较此时顶点的值和左右子树保持最小堆的性质 3. * 交换顶点和左右子树较小的值 4. 重复上述步骤直到已经成了最小堆或者遍历完 5. 注意可能存在左子树存在右子树不存在情况 6. * 不一定要遍历堆所有的元素达到堆的性质后会提前结束 * * return 返回被删除的元素 */public E removeTop() {if (data.isEmpty())return null;E removed data.get(0);// 因为一直交换的是最后的元素这儿将其保存E last data.get(data.size() - 1);data.set(0, last);data.remove(data.size() - 1);int parent 0;int leftChild parent * 2 1;int rightChild parent * 2 2;while (leftChild data.size() - 1) {int minIndex leftChild;// 右子树存在判断左右子树哪个小保存坐标// 如果不存在那么使用左子树的坐标// 保存较小元素的坐标可以省去考虑左右子树都存在只有左存在的情况if (rightChild data.size() - 1) {if (data.get(rightChild).compareTo(data.get(leftChild)) 0) {minIndex rightChild;}}if (data.get(minIndex).compareTo(last) 0) {data.set(parent, data.get(minIndex));data.set(minIndex, last);parent minIndex;leftChild parent * 2 1;rightChild parent * 2 2;} else {break; // 已经达到了最小堆的性质}}return removed;}Overridepublic String toString() {return data.toString();}}参考文章
