IT源码网

数据结构(七):堆

shasha 2021年06月22日 编程语言 537 0

 

一、 堆的概述

  堆是计算机中一种重要的数据结构,它是完全二叉树的数组体现。

二、 堆的特性

  2.1、堆是完全二叉树

  堆是完全二叉树的数据结构,除了树的最后一层结点不需要是满的,其他各层级从左到右都必须是满的,如果最后一层结点没有满,那么要求是左满右不满

   

  2.2、堆用数组来实现

  堆是用数组来存储上述完全二叉树的结点元素的,如根结点放在索引1位置处,根结点的左右子树放在2和3的位置,2和3的子结点又分别放在索引4,5和6,7的位置处,以此类推

  注:由于堆元素一般从数组的索引1处开始存储,所以0索引处不存放元素

  2.3、堆的父子结点在数组中有规律存在

  如一个节点的位置为索引k处,那么:

  父节点的位置:k/2

  左子树的位置:2*k

  右子树的位置:2*k+1

  所以在数组a[]中,我们可以通过a[k/2]来查找父节点,a[2*k]来查找左子结点,以此类推

   

  2.4、每个结点都大于两个子结点

  堆中每个结点元素都要大于两个子结点,两个子结点仅仅是都小于父节点,在左右子树中没有严格的要求

三、 堆的实现思路

  1、 增加堆元素

  堆元素的增加其实是往数组中去添加元素,做法是在数组最后插入元素,然后通过树节点的上浮和父节点比较大小来调整位置,最终使得既插入元素又保证堆有序。

  如下图演示插入结点S的过程:

  3.1.1 初始堆数组

   

  3.1.2 往数组末端插入结点S,即H的右子结点

   

  3.1.3 添加的元素S破坏了堆的有序性和父节点必须大于两个子结点的特性,故对S做上浮处理,和H替换

   

  3.1.4 上述上浮操作后堆依旧无序,再对S和P进行上浮替换,经此步替换后堆重新有序,并且满足堆的特性,堆元素插入成功

   

  2、 删除堆元素

  假设删除堆顶最大的元素,则步骤如下:

  3.2.1 交换堆顶和堆末结点的元素,并删除堆末元素,即将数组最末位元素置空

   

  3.2.2 由于此时根结点为H,破坏了堆的有序性和特性,所以此时将H与子结点较大值进行替换,以此进行直到H比左右子树都大,则堆重新有序

   

   

  3、 修改元素

  同数组的元素修改操作相同。

  4、 查找元素

  由于堆的数据元素以数组来表示,故查找元素可通过遍历数组索引查找对应的值实现

四、 堆的代码实现

  综上第三节描述,堆操作的思路,堆的实现代码如下:

public class Heap<T extends Comparable<T>> {

      

       //初始化堆

       private T[] items;

      

       //初始化个数

       private int N;

       /**

        * 构造方法,传入堆的初始大小

        * @param size

        */

       public Heap(int size) {

              items = (T[]) new Comparable[size + 1];

              N = 0;

       }

      

       /**

        * 判断堆中索引i处的值是否小于j处的值

        * @param i

        * @param j

        * @return

        */

       private boolean bigger(int i,int j) {

              return items[i].compareTo(items[j])>0;

       }

      

       /**

        * 元素位置的交换

        * @param col

        * @param i

        * @param j

        */

       private void switchPos(int i,int j) {

              T temp = items[i];

              items[i] = items[j];

              items[j] = temp;

       }

      

       /**

        * 删除堆中最大的元素,并且返回这个元素

        * @return

        */

       public T delMaxValue() {

              //获取根结点最大值

              T maxValue = items[1];

             

              //交换根结点和尾结点

              switchPos(1, N);

             

              //尾结点置空

              items[N] = null;

             

              //堆数量减1

              N--;

             

              //根结点下沉

              sink(1);

             

              return maxValue;

       }

      

       /**

        * 往堆中插入一个元素t

        * @param t

        */

       public void insert(T t) {

              items[++N] = t;

              swim(N);

       }

      

       /**

        * 使用上浮算法,使堆中索引k处的值能够处于一个正确的位置

        * @param k

        */

       private void swim(int k) {

              while(k>1) {

                     if(bigger(k/2, k)) {

                            switchPos(k/2, k);

                     }

                    

                     k = k/2;

              }

       }

      

       /**

        * 使用下沉算法,使堆中索引k处的值能够处于一个正确的位置

        * @param k

        */

       private void sink(int k) {

              while(2 * k <= N) {

                     int max;

                     //存在右子结点的情况

                     if(2*k+1 <= N) {

                            if(bigger(2*k,2*k+1)) {

                                   max = 2 * k;

                            }else {

                                   max = 2 * k + 1;

                            }

                     }else {

                            max = 2 * k;

                     }

                    

                     //当前结点不小,则退出

                     if(bigger(k, max)) {

                            break;

                     }

                    

                     switchPos(k, max);

                     k = max;

              }

       }

}

      

五、 堆的构造

  由上述堆的特性和操作可知,对堆的下沉操作,必须发生在堆长度N/2的位置处,因为树节点的左右节点为空,无法再进行下沉处理。

  因此,在构建一个堆时,我们可以创建一个新数组,将原数组0~N-1的元素拷贝至新数组的1-N处,并对N/2处往前的元素进行下沉处理,当N/2到1处的元素下沉完毕时,即堆构造完成,此时堆有序

  构造示例如下:

   

   

   

   

   

   

六、 堆排序及代码实现

  堆排序的实现思路:

  1、 如上所述构建好堆,使得初始堆有序和符合堆的特性

  2、 重复删除根结点的操作,即把根结点和堆末位结点交换,对根结点位置处的元素做下沉调整,下沉时分别比较左右节点,将较大值往上提

  3、 每次末位删除掉的根结点不再参与堆的删除和下沉操作

  4、 如上操作直到堆剩下一个元素为止

  如下所示为堆排序思路的演示图:

   

   

   

   

   

   

   

   

   

   

  堆排序的代码实现如下:

import java.util.Arrays;

public class HeapSort {

       /**

        * 堆排序

        * @param souce

        * @param heap

        */

       public static void sort(Comparable[] source) {

              //创建一个比原数组大1的heap

              Comparable[] heap = new Comparable[source.length+1];

             

              //构建heap

              initHeap(source, heap);

             

              //初始化heap最大位置索引

              int N = heap.length - 1;

             

              //排序操作,N=1时为排序完成(只有根结点)

              while(N!=1) {

                     //首先交换目标结点和最末结点的位置

                     switchPos(heap, 1, N);

                    

                     //排序完数量-1

                     N--;

                    

                     //在N范围内完成下沉调整

                     sink(heap, 1, N);

                    

              }

             

              //堆heap已有序,将有序的元素拷贝回原数组,即完成source的排序

              System.arraycopy(heap, 1, source, 0, source.length);

       }

      

       /**

        * 比较堆中两个元素的大小

        * @param heap

        * @param i

        * @param j

        * @return

        */

       public static boolean bigger(Comparable[] heap,int i,int j) {

              return heap[i].compareTo(heap[j]) > 0;

       }

      

       /**

        * 根据原数组,构建出初始堆

        * @param source

        * @param heap

        */

       public static void initHeap(Comparable[] source,Comparable[] heap) {

              //原数组拷贝到heap中

              System.arraycopy(source, 0, heap, 1, source.length);

             

              //对heap做初始化构造处理,从非叶子结点的N/2开始下沉,依次减1

              int heapL = heap.length;

              for(int i = heapL-1/2; i >= 1; i--) {

                     sink(heap, i, heapL-1);

              }

       }

      

       /**

        * 堆排序的下沉调整

        * @param heap

        * @param i

        * @param j

        */

       public static void sink(Comparable[] heap,int target,int range) {

              while(2 * target <= range) {

                     int max;

                     //存在右子结点的情况

                     if(2*target+1 <= range) {

                            if(bigger(heap,2*target,2*target+1)) {

                                   max = 2 * target;

                            }else {

                                   max = 2 * target + 1;

                            }

                     }else {

                            max = 2 * target;

                     }

                    

                     //当前结点不小,则退出

                     if(bigger(heap,target, max)) {

                            break;

                     }

                    

                     switchPos(heap,target, max);

                     target = max;

              }

       }

      

       /**

        * 元素位置的交换

        * @param col

        * @param i

        * @param j

        */

       private static void switchPos(Comparable[] heap,int i,int j) {

              Comparable temp = heap[i];

              heap[i] = heap[j];

              heap[j] = temp;

       }

      

       public static void main(String[] args) {

              String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};

              HeapSort.sort(arr);

              System.out.println(Arrays.toString(arr));

       }

}


评论关闭
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!