通过JAVA实现堆(优先队列)的数据结构

发表于   |   分类于 左手代码 计算机基础   |   阅读(497)   |   评论(0)

一、什么是堆

我们日常生活中经常见到各种堆，比如冬天的雪堆，施工的土堆，都是下面大，上面尖顶的样子，那么数据结构中的堆与日常生活中的堆有哪些异同呢？

日常生活中的堆与数据结构中的堆

1.堆的性质
  • 堆是一个完全二叉树(除了最后一层，其他层从左到右的节点都是满的)
  • 堆中的节点，都大于等于或小于等于其子节点
  • 堆通常使用数组来存储
2.堆的分类
  • 大顶堆
    • 所有节点大于或等于其子节点

大顶堆

  • 小顶堆
    • 所有节点大于或小于其子节点

小顶堆

二、通过数组实现堆元素的存储

因为堆是一个完全二叉树

通过数组来存储堆元素

三、通过JAVA实现堆的数据结构

注：这里以小顶堆为例

1.定义堆结构：
  • size : 树节点个数
  • nodes : 节点值集合
  1. public class MyArrayHeap<T> {
  2.     /**
  3.      * 节点个数
  4.      */
  5.     private int size;
  7.     /**
  8.      * 节点数组
  9.      */
  10.     private T[] nodes;
  12.     /**
  13.      * 最小容量
  14.      */
  15.     private static final int MIN_CAPACITY = 8;
  16. }
2.添加节点
(1)添加节点的流程图

添加节点的流程图

  • 将新节点添加到树的末尾，即数组的末尾
  • 再将插入的节点与其父节点做对比，如果父节点大于插入的节点，则交换二者的位置，直到插入的节点比父节点小为止
(2)添加节点的实现
  1.     /**
  2.      * 添加节点
  3.      * @param element
  4.      * @return
  5.      */
  6.     public boolean add(T element) {
  7.         //1.如果原数组是空数组，直接将元素插入进去，当作根节点
  8.         if (size == 0) {
  9.             nodes[0] = element;
  10.             return true;
  11.         }
  12.         //2.如果数组长度达到节点的个数，则扩容
  13.         if (size >= nodes.length ) {
  14.             ensureCapacity(size * 2 + 1);
  15.         }
  16.         //3.定义插入位置的索引index，默认插入到树的最后
  17.         int index = size;
  18.         Comparable<T> node = (Comparable<T>) element;
  19.         //4.循环比较插入节点与当前的父节点的大小，如果大于父节点，不用交换，否则，要交换位置
  20.         while (index > 0) {
  21.             //父节点的索引
  22.             int parent = (index - 1) / 2;
  23.             //父节点的元素值
  24.             T e = nodes[parent];
  25.             //如果当前插入节点(子节点)比父节点大，那么当前位置就是要插入的位置
  26.             if (node.compareTo(e) >= 0) {
  27.                 break;
  28.             }
  29.             //插入节点位置与父节点位置交换
  30.             nodes[index] = e;
  31.             index = parent;
  32.         }
  33.         //最后得到插入的位置
  34.         nodes[index] = element;
  35.         return true;
  36.     }
3.删除节点
(1)删除节点的流程图

删除节点的流程图

  • 删除根节点
  • 选出新的父节点
(2)删除节点的实现
  1.  /**
  2.      * 删除也叫删除最小元素
  3.      * @return
  4.      */
  5.     public boolean remove() {
  6.         if (size == 0) {
  7.             return false;
  8.         }
  9.         //1.定义被最后替换的索引值
  10.         int index = 0;
  11.         //2.最后一个元素，也就是最后被移动的元素
  12.         T element = nodes[size - 1];
  13.         Comparable<T> node = (Comparable<T>) element;
  14.         //父节点个数half
  15.         int half = size / 2;
  16.         while (index < half) {
  17.             //子节点索引及子节点值
  18.             int child = index * 2 + 1;
  19.             T obj = nodes[child];
  20.             //右子节点索引
  21.             int rightChild = child + 1;
  22.             //如果右子节点比左子节点小，那么右子节点移动到左子节点的位置
  23.             if (rightChild < size && ((Comparable<T>) obj).compareTo(nodes[rightChild]) > 0) {
  24.                 child = rightChild;
  25.                 obj = nodes[child];
  26.             }
  27.             if (node.compareTo(obj) <= 0) {
  28.                 break;
  29.             }
  30.             nodes[index] = obj;
  31.             index = child;
  32.         }
  33.         //最后一个元素仍然存储在数组最后一个位置上
  34.         nodes[index] = element;
  35.         size --;
  36.         return true;
  37.     }
4.完整实现
  1. package main.java.com.shixinke.java.demo.dataStruct;
  3. public class MyArrayHeap<T> {
  4.     /**
  5.      * 节点个数
  6.      */
  7.     private int size;
  9.     /**
  10.      * 节点数组
  11.      */
  12.     private T[] nodes;
  14.     /**
  15.      * 最小容量
  16.      */
  17.     private static final int MIN_CAPACITY = 8;
  19.     public MyArrayHeap() {
  20.         clearHeap(MIN_CAPACITY);
  21.     }
  23.     public MyArrayHeap(int capacity) {
  24.         clearHeap(capacity);
  25.     }
  27.     public void clear() {
  28.         clearHeap(MIN_CAPACITY);
  29.     }
  31.     /**
  32.      * 获取节点个数
  33.      * @return
  34.      */
  35.     public int size() {
  36.         return size;
  37.     }
  39.     /**
  40.      * 是否为空堆
  41.      * @return
  42.      */
  43.     public boolean isEmpty() {
  44.         return size == 0;
  45.     }
  47.     /**
  48.      * 添加节点
  49.      * @param element
  50.      * @return
  51.      */
  52.     public boolean add(T element) {
  53.         //1.如果原数组是空数组，直接将元素插入进去，当作根节点
  54.         if (size == 0) {
  55.             nodes[0] = element;
  56.             size = 1;
  57.             return true;
  58.         }
  59.         //2.如果数组长度达到节点的个数，则扩容
  60.         if (size >= nodes.length ) {
  61.             ensureCapacity(size * 2 + 1);
  62.         }
  63.         //3.定义插入位置的索引index，默认插入到树的最后
  64.         int index = size;
  65.         Comparable<T> node = (Comparable<T>) element;
  66.         //4.循环比较插入节点与当前的父节点的大小，如果大于父节点，不用交换，否则，要交换位置
  67.         while (index > 0) {
  68.             //父节点的索引
  69.             int parent = (index - 1) / 2;
  70.             //父节点的元素值
  71.             T e = nodes[parent];
  72.             //如果当前插入节点(子节点)比父节点大，那么当前位置就是要插入的位置
  73.             if (node.compareTo(e) >= 0) {
  74.                 break;
  75.             }
  76.             //插入节点位置与父节点位置交换
  77.             nodes[index] = e;
  78.             index = parent;
  79.         }
  80.         //最后得到插入的位置
  81.         nodes[index] = element;
  82.         size ++;
  83.         return true;
  84.     }
  86.     /**
  87.      * 删除也叫删除最小元素
  88.      * @return
  89.      */
  90.     public boolean remove() {
  91.         if (size == 0) {
  92.             return false;
  93.         }
  94.         //1.定义被最后替换的索引值
  95.         int index = 0;
  96.         //2.最后一个元素，也就是最后被移动的元素
  97.         T element = nodes[size - 1];
  98.         Comparable<T> node = (Comparable<T>) element;
  99.         //父节点个数half
  100.         int half = size / 2;
  101.         while (index < half) {
  102.             //子节点索引及子节点值
  103.             int child = index * 2 + 1;
  104.             T obj = nodes[child];
  105.             //右子节点索引
  106.             int rightChild = child + 1;
  107.             //如果右子节点比左子节点小，那么右子节点移动到左子节点的位置
  108.             if (rightChild < size && ((Comparable<T>) obj).compareTo(nodes[rightChild]) > 0) {
  109.                 child = rightChild;
  110.                 obj = nodes[child];
  111.             }
  112.             if (node.compareTo(obj) <= 0) {
  113.                 break;
  114.             }
  115.             nodes[index] = obj;
  116.             index = child;
  117.         }
  118.         //最后一个元素仍然存储在数组最后一个位置上
  119.         nodes[index] = element;
  120.         size --;
  121.         return true;
  122.     }
  124.     private void clearHeap(int capacity) {
  125.         size = 0;
  126.         ensureCapacity(capacity);
  127.     }
  129.     /**
  130.      * 扩容
  131.      * @param capacity
  132.      */
  133.     private void ensureCapacity(int capacity) {
  134.         if (capacity < size) {
  135.             return;
  136.         }
  137.         T[] oldNodes = nodes;
  138.         nodes = (T[]) new Object[capacity];
  139.         for (int i = 0; i< size; i++) {
  140.             nodes[i] = oldNodes[i];
  141.         }
  142.     }
  144.     //打印节点
  145.     public void print() {
  146.         System.out.println();
  147.         System.out.print("[");
  148.         for (int i = 0; i < size; i++) {
  149.             System.out.print(i+"="+nodes[i]);
  150.             if (i < size -1) {
  151.                 System.out.print(",");
  152.             }
  153.         }
  154.         System.out.print("]");
  155.         System.out.println();
  157.     }
  159.     //演示测试　
  160.     public static void main(String[] args) {
  161.         MyArrayHeap<Integer> heap = new MyArrayHeap<Integer>();
  162.         heap.add(21);
  163.         heap.add(23);
  164.         heap.add(25);
  165.         heap.add(24);
  166.         heap.add(26);
  167.         heap.add(27);
  168.         heap.add(29);
  169.         heap.add(28);
  170.         heap.add(30);
  173.         //heap.print();  //[0=21,1=23,2=25,3=24,4=26,5=27,6=29,7=28,8=30]
  174.         heap.remove();
  175.         heap.print();    //[0=23,1=24,2=25,3=28,4=26,5=27,6=29,7=30]
  176.     }
  181. }

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开