`

彻底弄懂最大堆的四种操作(图解+程序)（JAVA）

 
阅读更多

http://128kj.iteye.com/blog/1728555

堆有最大堆和最小堆之分，最大堆就是每个节点的值都>=其左右孩子（如果有的话）值的完全二叉树。最小堆便是每个节点的值都<=其左右孩子值的完全二叉树。 

  设有n个元素的序列{k1,k2,...,kn},当且仅当满足下列关系时,称之为堆。 
 

堆的三种基本操作(以下以最大堆为例)： 
⑴最大堆的插入   

    由于需要维持完全二叉树的形态，需要先将要插入的结点x放在最底层的最右边，插入后满 足完全二叉树的特点； 
  然后把x依次向上调整到合适位置满足堆的性质,例如下图中插入80,先将80放在最后,然后两次上浮到合适位置. 
  时间：O(logn)。  “结点上浮” 
 

程序实现: 

Java代码  收藏代码
  1. //向最大堆中插入元素, heap:存放堆元素的数组  
  2.    public static void insert(List<Integer> heap, int value) {   
  3.       //在数组的尾部添加  
  4.        if(heap.size()==0)  
  5.          heap.add(0);//数组下标为0的位置不放元素  
  6.        heap.add(value);   
  7.        //开始上升操作   
  8.       // heapUp2(heap, heap.size() - 1);   
  9.        heapUp(heap, heap.size() - 1);   
  10.   
  11.    }   
  12.   
  13.    //上升，让插入的数和父节点的数值比较，当大于父节点的时候就和父节点的值相交换   
  14.    public static void heapUp(List<Integer> heap, int index) {   
  15.   
  16.        //注意由于数值是从下标为1开始，当index = 1的时候，已经是根节点了   
  17.        if (index > 1) {   
  18.            //求出父亲的节点   
  19.            int parent = index / 2;   
  20.   
  21.            //获取相应位置的数值   
  22.            int parentValue = (Integer) heap.get(parent);   
  23.            int indexValue = (Integer) heap.get(index);   
  24.            //如果父亲节点比index的数值小，就交换二者的数值   
  25.            if (parentValue < indexValue) {   
  26.                //交换数值   
  27.                swap(heap, parent, index);   
  28.                //递归调用   
  29.                heapUp(heap, parent);   
  30.            }   
  31.   
  32.        }   
  33.    }   



⑵删除 
   操作原理是：当删除节点的数值时，原来的位置就会出现一个孔,填充这个孔的方法就是， 
把最后的叶子的值赋给该孔并下调到合适位置，最后把该叶子删除。 
  
如图中要删除72,先用堆中最后一个元素来35替换72,再将35下沉到合适位置,最后将叶子节点删除。 
　　“结点下沉” 

 

Java代码  收藏代码
  1. 程序:  
  2.  /** 
  3.      * 删除堆中位置是index处的节点 
  4.      * 操作原理是：当删除节点的数值时，原来的位置就会出现一个孔 
  5.      * 填充这个孔的方法就是，把最后的叶子的值赋给该孔，最后把该叶子删除 
  6.      * @param heap  
  7.      */   
  8.     public static void delete(List<Integer> heap,int index) {   
  9.         //把最后的一个叶子的数值赋值给index位置   
  10.         heap.set(index, heap.get(heap.size() - 1));   
  11.         //下沉操作   
  12.         //heapDown2(heap, index);   
  13.         heapDown(heap, index);   
  14.         //把最后一个位置的数字删除   
  15.         heap.remove(heap.size() - 1);   
  16.     }   
  17.   
  18.   
  19.     /** 
  20.      * 递归实现 
  21.      * 删除堆中一个数据的时候，根据堆的性质，应该把相应的位置下移，才能保持住堆性质不变 
  22.      * @param heap 保持堆元素的数组 
  23.      * @param index 被删除的那个节点的位置 
  24.      */   
  25.     public static void heapDown(List<Integer> heap, int index) {   
  26.         //因为第一个位置存储的是空值，不在考虑之内   
  27.         int n = heap.size() - 2;   
  28.    
  29.         //记录最大的那个儿子节点的位置   
  30.         int child = -1;   
  31.    
  32.         //2*index>n说明该节点没有左右儿子节点了，那么就返回   
  33.         if (2 * index > n) {   
  34.             return;   
  35.         } //如果左右儿子都存在   
  36.         else if (2 * index < n) {   
  37.    
  38.             //定义左儿子节点   
  39.             child = 2 * index;   
  40.             //如果左儿子小于右儿子的数值，取右儿子的下标   
  41.             if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {   
  42.                 child++;   
  43.             }   
  44.    
  45.         }//如果只有一个儿子（左儿子节点）   
  46.         else if (2 * index == n) {   
  47.             child = 2 * index;   
  48.         }   
  49.    
  50.         if ((Integer) heap.get(child) > (Integer) heap.get(index)) {   
  51.             //交换堆中的child，和index位置的值   
  52.             swap(heap, child, index);   
  53.    
  54.             //完成交换后递归调用，继续下降   
  55.             heapDown(heap, child);   
  56.         }   
  57.     }   
  58.    



⑶初始化 
方法1：插入法： 
  从空堆开始，依次插入每一个结点，直到所有的结点全部插入到堆为止。 
  时间：O(n*log(n)) 
  方法2：调整法： 
    序列对应一个完全二叉树；从最后一个分支结点（n div 2）开始，到根（1）为止，依次对每个分支结点进行调整（下沉），以便形成以每个分支结点为根的堆，当最后对树根结点进行调整后，整个树就变成了一个堆。 
  时间：O(n) 
对如图的序列,要使其成为堆,我们从最后一个分支结点(10/2),其值为72开始,依次对每个分支节点53,18,36 45进行调整(下沉). 
 
 
 

Java代码  收藏代码
  1. 程序:  
  2.   
  3.      /*根据树的性质建堆，树节点前一半一定是分支节点，即有孩子的，所以我们从这里开始调整出初始堆*/    
  4.      public static void adjust(List<Integer> heap){  
  5.         for (int i = heap.size() / 2; i > 0; i--)    
  6.             adjust(heap,i, heap.size()-1);    
  7.   
  8.             
  9.         System.out.println("=================================================");  
  10.         System.out.println("调整后的初始堆：");  
  11.           print(heap);  
  12.       }  
  13.   
  14.     /**  
  15.      * 调整堆，使其满足堆得定义  
  16.      * @param i  
  17.      * @param n  
  18.      */    
  19.     public static void adjust(List<Integer> heap,int i, int n) {    
  20.          
  21.         int child;    
  22.         for (; i <= n / 2; ) {    
  23.             child = i * 2;    
  24.             if(child+1<=n&&heap.get(child)<heap.get(child+1))    
  25.                 child+=1;/*使child指向值较大的孩子*/    
  26.             if(heap.get(i)< heap.get(child)){    
  27.                 swap(heap,i, child);    
  28.                 /*交换后，以child为根的子树不一定满足堆定义，所以从child处开始调整*/    
  29.                 i = child;    
  30.                  
  31.             }  else break;  
  32.         }    
  33.     }    



(4)最大堆排序  

Java代码  收藏代码
  1. //对一个最大堆heap排序  
  2.    public static void heapSort(List<Integer> heap) {    
  3.         
  4.        for (int i = heap.size()-1; i > 0; i--) {    
  5.         /*把根节点跟最后一个元素交换位置，调整剩下的n-1个节点，即可排好序*/    
  6.            swap(heap,1, i);    
  7.            adjust(heap,1, i - 1);    
  8.        }    
  9.    }    



(5)完整的代码 

Java代码  收藏代码
  1. import java.util.*;   
  2.    
  3. /** 
  4.  *实现的最大堆的插入和删除操作 
  5.  * @author Arthur 
  6.  */   
  7. public class Heap {   
  8.   
  9.      /** 
  10.      * 删除堆中位置是index处的值 
  11.      * 操作原理是：当删除节点的数值时，原来的位置就会出现一个孔 
  12.      * 填充这个孔的方法就是，把最后的叶子的值赋给该孔，最后把该叶子删除 
  13.      * @param heap 一个最大堆 
  14.      */   
  15.     public static void delete(List<Integer> heap,int index) {   
  16.         //把最后的一个叶子的数值赋值给index位置   
  17.         heap.set(index, heap.get(heap.size() - 1));   
  18.         //下沉操作   
  19.         //heapDown2(heap, index);   
  20.         heapDown(heap, index); //节点下沉  
  21.         //把最后一个位置的数字删除   
  22.         heap.remove(heap.size() - 1);   
  23.     }   
  24.    
  25.    
  26.     /**  
  27.      * 节点下沉递归实现 
  28.      * 删除一个堆中一个数据的时候，根据堆的性质，应该把相应的位置下移，才能保持住堆性质不变 
  29.      * @param heap 保持最大堆元素的数组 
  30.      * @param index 被删除的那个节点的位置 
  31.      */   
  32.     public static void heapDown(List<Integer> heap, int index) {   
  33.         //因为第一个位置存储的是空值，不在考虑之内   
  34.         int n = heap.size() - 2;   
  35.    
  36.         //记录最大的那个儿子节点的位置   
  37.         int child = -1;   
  38.    
  39.         //2*index>n说明该节点没有左右儿子节点了，那么就返回   
  40.         if (2 * index > n) {   
  41.             return;   
  42.         } //如果左右儿子都存在   
  43.         else if (2 * index < n) {   
  44.    
  45.             //定义左儿子节点   
  46.             child = 2 * index;   
  47.             //如果左儿子小于右儿子的数值，取右儿子的下标   
  48.             if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {   
  49.                 child++;   
  50.             }   
  51.    
  52.         }//如果只有一个儿子（左儿子节点）   
  53.         else if (2 * index == n) {   
  54.             child = 2 * index;   
  55.         }   
  56.    
  57.         if ((Integer) heap.get(child) > (Integer) heap.get(index)) {   
  58.             //交换堆中的child，和index位置的值   
  59.             swap(heap, child, index);   
  60.    
  61.             //完成交换后递归调用，继续下降   
  62.             heapDown(heap, child);   
  63.         }   
  64.     }   
  65.    
  66.     //非递归实现   
  67.     public static void heapDown2(List<Integer> heap, int index) {   
  68.         int child = 0;//存储左儿子的位置   
  69.    
  70.         int temp = (Integer) heap.get(index);   
  71.         int n = heap.size() - 2;   
  72.         //如果有儿子的话   
  73.         for (; 2 * index <= n; index = child) {   
  74.             //获取左儿子的位置   
  75.             child = 2 * index;   
  76.             //如果只有左儿子   
  77.             if (child == n) {   
  78.                 child = 2 * index;   
  79.             } //如果右儿子比左儿子的数值大   
  80.             else if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) {   
  81.                 child++;   
  82.             }   
  83.    
  84.             //如果数值最大的儿子比temp的值大   
  85.             if ((Integer) heap.get(child) >temp) {   
  86.                 //交换堆中的child，和index位置的值   
  87.                 swap(heap, child, index);   
  88.             } else {   
  89.                 break;   
  90.             }   
  91.         }   
  92.     }   
  93.    
  94.       
  95.      //打印链表   
  96.     public static void print(List<Integer> list) {   
  97.         for (int i = 1; i < list.size(); i++) {   
  98.             System.out.print(list.get(i) + " ");   
  99.         }   
  100.         System.out.println();  
  101.     }   
  102.    
  103.     //把堆中的a,b位置的值互换   
  104.     public static void swap(List<Integer> heap, int a, int b) {   
  105.         //临时存储child位置的值   
  106.         int temp = (Integer) heap.get(a);   
  107.    
  108.         //把index的值赋给child的位置   
  109.         heap.set(a, heap.get(b));   
  110.    
  111.         //把原来的child位置的数值赋值给index位置   
  112.         heap.set(b, temp);   
  113.     }   
  114.    
  115.     //向最大堆中插入元素   
  116.     public static void insert(List<Integer> heap, int value) {   
  117.            //在数组的尾部添加要插入的元素  
  118.         if(heap.size()==0)  
  119.           heap.add(0);//数组下标为0的位置不放元素  
  120.         heap.add(value);   
  121.         //开始上升操作   
  122.        // heapUp2(heap, heap.size() - 1);   
  123.         heapUp(heap, heap.size() - 1);   
  124.    
  125.     }   
  126.    
  127.     //节点上浮，让插入的数和父节点的数值比较，当大于父节点的时候就和节点的值相交换   
  128.     public static void heapUp(List<Integer> heap, int index) {   
  129.    
  130.         //注意由于数值是从小标为一开始，当index = 1的时候，已经是根节点了   
  131.         if (index > 1) {   
  132.             //保存父亲的节点   
  133.             int parent = index / 2;   
  134.    
  135.             //获取相应位置的数值   
  136.             int parentValue = (Integer) heap.get(parent);   
  137.             int indexValue = (Integer) heap.get(index);   
  138.             //如果父亲节点比index的数值小，就交换二者的数值   
  139.             if (parentValue < indexValue) {   
  140.                 //交换数值   
  141.                 swap(heap, parent, index);   
  142.                 //递归调用   
  143.                 heapUp(heap, parent);   
  144.             }   
  145.    
  146.         }   
  147.     }   
  148.    
  149.     //非递归实现   
  150.     public static void heapUp2(List<Integer> heap, int index) {   
  151.         int parent = 0;   
  152.         for (; index > 1; index /= 2) {   
  153.             //获取index的父节点的下标   
  154.             parent = index / 2;   
  155.    
  156.             //获得父节点的值   
  157.             int parentValue = (Integer) heap.get(parent);   
  158.             //获得index位置的值   
  159.             int indexValue = (Integer) heap.get(index);   
  160.                
  161.             //如果小于就交换   
  162.             if (parentValue < indexValue) {   
  163.                 swap(heap, parent, index);   
  164.             }   
  165.         }   
  166.     }   
  167.   
  168.      /*根据树的性质建堆，树节点前一半一定是分支节点，即有孩子的，所以我们从这里开始调整出初始堆*/    
  169.      public static void adjust(List<Integer> heap){  
  170.         for (int i = heap.size() / 2; i > 0; i--)    
  171.             adjust(heap,i, heap.size()-1);    
  172.   
  173.             
  174.         System.out.println("=================================================");  
  175.         System.out.println("调整后的初始堆：");  
  176.           print(heap);  
  177.       }  
  178.   
  179.     /**  
  180.      * 调整堆，使其满足堆得定义  
  181.      * @param i  
  182.      * @param n  
  183.      */    
  184.     public static void adjust(List<Integer> heap,int i, int n) {    
  185.          
  186.         int child;    
  187.         for (; i <= n / 2; ) {    
  188.             child = i * 2;    
  189.             if(child+1<=n&&heap.get(child)<heap.get(child+1))    
  190.                 child+=1;/*使child指向值较大的孩子*/    
  191.             if(heap.get(i)< heap.get(child)){    
  192.                 swap(heap,i, child);    
  193.                 /*交换后，以child为根的子树不一定满足堆定义，所以从child处开始调整*/    
  194.                 i = child;    
  195.                  
  196.             }  else break;  
  197.         }    
  198.     }    
  199.     
  200.    //对一个最大堆heap排序  
  201.     public static void heapSort(List<Integer> heap) {    
  202.          
  203.         for (int i = heap.size()-1; i > 0; i--) {    
  204.         /*把根节点跟最后一个元素交换位置，调整剩下的n-1个节点，即可排好序*/    
  205.             swap(heap,1, i);    
  206.             adjust(heap,1, i - 1);    
  207.         }    
  208.     }    
  209.   
  210.    public static void main(String args[]) {   
  211.         List<Integer> array = new ArrayList<Integer>(Arrays.asList(null, 1, 2, 5, 10, 3, 7, 11, 15, 17, 20, 9, 15, 8, 16));  
  212.         adjust(array);//调整使array成为最大堆  
  213.          
  214.         delete(array,8);//堆中删除下标是8的元素  
  215.         System.out.println("删除后");  
  216.         print(array);  
  217.   
  218.         insert(array, 99);//堆中插入  
  219.         print(array);   
  220.   
  221.         heapSort(array);//排序  
  222.         System.out.println("将堆排序后:");  
  223.         print(array);  
  224.         System.out.println("-------------------------");  
  225.         List<Integer> array1=new ArrayList<Integer>();  
  226.         insert(array1,0);  
  227.         insert(array1, 1);insert(array1, 2);insert(array1, 5);  
  228.         insert(array1, 10);insert(array1, 3);insert(array1, 7);  
  229.         insert(array1, 11);insert(array1, 15); insert(array1, 17);  
  230.         insert(array1, 20);insert(array1, 9);  
  231.         insert(array1, 15);insert(array1, 8);insert(array1, 16);  
  232.         print(array1);  
  233.           
  234.         System.out.println("==============================");  
  235.         array=new ArrayList<Integer>(Arrays.asList(null,45,36,18,53,72,30,48,93,15,35));  
  236.         adjust(array);  
  237.           insert(array, 80);//堆中插入  
  238.           print(array);  
  239.          delete(array,2);//堆中删除80的元素  
  240.          print(array);  
  241.          delete(array,2);//堆中删除72的元素  
  242.          print(array);  
  243.                 
  244.     }   
  245. }   



程序运行: 
D:\java>java   Heap 
================================================= 
调整后的初始堆： 
20 17 16 15 9 15 11 1 10 3 2 7 8 5 
删除后 
20 17 16 15 9 15 11 5 10 3 2 7 8 
99 17 20 15 9 15 16 5 10 3 2 7 8 11 
将堆排序后: 
2 3 5 7 8 9 10 11 15 15 16 17 20 99 
------------------------- 
20 17 16 10 15 9 15 0 5 2 11 1 7 3 8 
============================== 
================================================= 
调整后的初始堆： 
93 72 48 53 45 30 18 36 15 35 
93 80 48 53 72 30 18 36 15 35 45 
93 72 48 53 45 30 18 36 15 35 
93 53 48 36 45 30 18 35 15 
源码下载

 

分享到：
| 理解 A=B。C++拷贝构造函数(深拷贝，浅拷 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics