Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to insert and delete heap in programming". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn how to insert and delete the heap in programming.

Insert / / insert elements into the maximum heap, heap: array public static void insert (List heap, int value) {/ / add if (heap.size () = = 0) heap.add (0) to the end of the array; / / the element heap.add (value) is not placed at the position marked 0 in the array / / start rising operation / / heapUp2 (heap, heap.size ()-1); heapUp (heap, heap.size ()-1) } / / rise, so that the number of inserts is compared with the value of the parent node, and when it is larger than the parent node, it is exchanged with the value of the parent node public static void heapUp (List heap, int index) {/ / Note that since the value starts with the subscript 1, when index = 1 It is already the root node if (index > 1) {/ / find the parent node int parent = index / 2 / / get the value of the corresponding position int parentValue = (Integer) heap.get (parent); int indexValue = (Integer) heap.get (index); / / if the parent node is smaller than the value of index, exchange the value if (parentValue) of the two

< indexValue) { //交换数值 swap(heap, parent, index); //递归调用 heapUp(heap, parent); } } }最大堆的删除 /** * 删除堆中位置是index处的节点 * 操作原理是：当删除节点的数值时，原来的位置就会出现一个孔 * 填充这个孔的方法就是，把最后的叶子的值赋给该孔，最后把该叶子删除 * @param heap */ public static void delete(List heap,int index) { //把最后的一个叶子的数值赋值给index位置 heap.set(index, heap.get(heap.size() - 1)); //下沉操作 //heapDown2(heap, index); heapDown(heap, index); //把最后一个位置的数字删除 heap.remove(heap.size() - 1); } /** * 递归实现 * 删除堆中一个数据的时候，根据堆的性质，应该把相应的位置下移，才能保持住堆性质不变 * @param heap 保持堆元素的数组 * @param index 被删除的那个节点的位置 */ public static void heapDown(List heap, int index) { //因为第一个位置存储的是空值，不在考虑之内 int n = heap.size() - 2; //记录最大的那个儿子节点的位置 int child = -1; //2*index>

If n means there is no left or right son node in the node, then return if (2 * index > n) {return;} / / if both left and right sons have else if (2 * index)

< n) { //定义左儿子节点 child = 2 * index; //如果左儿子小于右儿子的数值，取右儿子的下标 if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) { child++; } }//如果只有一个儿子（左儿子节点） else if (2 * index == n) { child = 2 * index; } if ((Integer) heap.get(child) >

(Integer) heap.get (index) {/ / switch the child in the heap, and the value of the index location swap (heap, child, index); / / Recursive call after the exchange is completed, continue to decrease the heapDown (heap, child) }} at this point, I believe you have a deeper understanding of "how to insert and delete the heap in programming". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.