堆

概述

　　堆是一种完全二叉树，分为两种类型：

　　　　大顶堆：每一个非叶子结点均不小于其孩子结点。

　　　　小顶堆：每一个非叶子结点均不大于其孩子结点。

　　堆中根结点的位置称为堆顶，最后结点的位置称为堆尾，结点个数称为堆长度。由于结点从1开始编号，所以堆尾的结点编号等于其堆长度。

　　堆有以下特性：

　　　　a.对于大顶堆，堆顶元素是最大值。对于小顶堆，堆顶元素是最小值。

　　　　b.对于大顶堆，堆顶的左右孩子结点中元素值较大的为第二大值。对于小顶堆，堆顶的左右孩子结点中元素值较小的为第二小值。

　　堆的特性常被用于实现排序。

堆

　　堆常用的操作有：

　　　　插入：在堆尾后插入新结点，然后调整堆结构。

　　　　修改：修改某个结点的元素值，然后调整堆结构。

　　　　删除：将某个结点与堆尾交换，然后删除堆尾，最后调整堆结构。

　　　　调整：在插入、修改、删除操作后，可能导致结构不再符合堆的特性，需要作出调整。

　　堆接口的定义如下：

 1 /**
 2  * 堆
 3  */
 4 public interface Heap<E extends Comparable<E>> {
 5 
 6     /**
 7      * 堆类型
 8      */
 9     enum Tag {
10         /**
11          * 大顶堆
12          */
13         GREAT, 
14 
15         /**
16          * 小顶堆
17          */
18         LESS;
19     }
20 
21     /**
22      * 添加结点
23      * @param e
24      */
25     void add(E e);
26 
27     /**
28      * 修改指定结点的元素值，并重新调整
29      * @param index
30      * @param e
31      * @throws HeapException
32      */
33     void set(int index, E e) throws HeapException;
34 
35     /**
36      * 删除指定结点的元素值
37      * @param index
38      * @throws HeapException
39      */
40     void remove(int index) throws HeapException;
41 
42     /**
43      * 判断是否为空堆
44      * @return
45      */
46     boolean isEmpty();
47 
48     /**
49      * 获取堆中元素个数
50      * @return
51      */
52     int getNum();
53 
54     /**
55      * 判断是否为大顶堆
56      * @return
57      */
58     boolean isGreatHeap();
59 
60     /**
61      * 判断是否为小顶堆
62      * @return
63      */
64     boolean isLessHeap();
65 
66 }

Heap

　　其抽象类定义如下：

 1 public abstract class AbstractHeap<E extends Comparable<E>> implements Heap<E> {
 2 
 3     /**
 4      * 堆长度
 5      */
 6     protected int num;
 7 
 8     /**
 9      * 堆类型
10      */
11     protected Tag tag;
12 
13     /**
14      * 计算父结点编号
15      * @param index
16      * @return
17      */
18     protected int getParentIndex(int index) {
19         return index % 2 == 0 ? index / 2 : (index - 1) / 2;
20     }
21 
22     /**
23      * 计算左子结点编号
24      * @param index
25      * @return
26      */
27     protected int getLchildIndex(int index) {
28         return 2 * index;
29     }
30 
31     /**
32      * 计算右子结点编号
33      * @param index
34      * @return
35      */
36     protected int getRchildIndex(int index) {
37         return 2 * index + 1;
38     }
39 
40     /**
41      * 检查是否为空堆
42      * @throws HeapException
43      */
44     protected void checkEmpty() throws HeapException {
45         if (isEmpty()) throw new HeapException("堆中没有元素！");
46     }
47 
48     /**
49      * 检查编号是否超出范围
50      * @param index
51      * @throws HeapException
52      */
53     protected void checkOutOfBounds(int index) throws HeapException {
54         checkEmpty();
55         if (index < 1) throw new HeapException("编号" + index + "必须为正数！");
56         if (index > num) throw new HeapException("编号" + index + "超出范围！");
57     }
58 
59     @Override
60     public boolean isEmpty() {
61         return num == 0;
62     }
63 
64     @Override
65     public int getNum() {
66         return num;
67     }
68 
69     @Override
70     public boolean isGreatHeap() {
71         return tag == Tag.GREAT;
72     }
73 
74     @Override
75     public boolean isLessHeap() {
76         return tag == Tag.LESS;
77     }
78 
79 }

AbstractHeap

　　堆的存储结构分为顺序存储和链式存储。

　　顺序存储结构如下：

  1 public class SqHeap<E extends Comparable<E>> extends AbstractHeap<E> {
  2 
  3     protected Object[] elem;
  4     protected int size;
  5     protected int increment;
  6 
  7     public SqHeap(Tag tag) {
  8         this (3, tag, 5);
  9     }
 10 
 11     public SqHeap(int inc, Tag tag, int size) {
 12         this.tag = tag;
 13         this.size = size;
 14         increment = inc;
 15         elem = new Object[size];
 16     }
 17 
 18     @SuppressWarnings("unchecked")
 19     public SqHeap(Tag tag, E... elems) {
 20         this (3, tag, elems);
 21     }
 22 
 23     @SuppressWarnings("unchecked")
 24     public SqHeap(int inc, Tag tag, E... elems) {
 25         this (inc, tag, elems.length);
 26         for (E e : elems) add(e);
 27     }
 28 
 29     @SuppressWarnings({ "unchecked" })
 30     @Override
 31     public void add(E e) {
 32         num++;
 33         if (num > elem.length) {
 34             Object[] elem = new Object[num + 3];
 35             System.arraycopy(this.elem, 0, elem, 0, this.elem.length);
 36             this.elem = elem;
 37         }
 38         if (num == 1) {
 39             elem[0] = e;
 40         } else {
 41             int index = num;
 42             for (int parent = getParentIndex(num); parent > 0; parent = getParentIndex(parent)) {
 43                 if (tag == Tag.GREAT) {
 44                     if (e.compareTo((E) elem[parent - 1]) > 0) {
 45                         elem[index - 1] = elem[parent - 1];
 46                         index = parent;
 47                     } else {
 48                         break;
 49                     }
 50                 } else {
 51                     if (e.compareTo((E) elem[parent - 1]) < 0) {
 52                         elem[index - 1] = elem[parent - 1];
 53                         index = parent;
 54                     } else {
 55                         break;
 56                     }
 57                 }
 58             }
 59             elem[index - 1] = e;
 60         }
 61     }
 62 
 63     private void swap(int i, int j) {
 64         Object temp = elem[i];
 65         elem[i] = elem[j];
 66         elem[j] = temp;
 67     }
 68 
 69     @SuppressWarnings({ "unchecked", "preview" })
 70     private void adjust(int index) {
 71         switch (tag) {
 72             case GREAT -> {
 73                 int parent = getParentIndex(index);
 74                 if (parent >= 1 && ((E) elem[index - 1]).compareTo((E) elem[parent - 1]) > 0) {
 75                     swap(index - 1, parent - 1);
 76                     adjust(parent);
 77                 } else if (index <= num / 2) {
 78                     int lchild = getLchildIndex(index);
 79                     int rchild = getRchildIndex(index);
 80                     if (rchild > num || ((E) elem[lchild - 1]).compareTo((E) elem[rchild - 1]) > 0) {
 81                         if (((E) elem[index - 1]).compareTo((E) elem[lchild - 1]) < 0) {
 82                             swap(index - 1, lchild - 1);
 83                             adjust(lchild);
 84                         }
 85                     } else {
 86                         if (((E) elem[index - 1]).compareTo((E) elem[rchild - 1]) < 0) {
 87                             swap(index - 1, rchild - 1);
 88                             adjust(rchild);
 89                         }
 90                     }
 91                 }
 92             }
 93             case LESS -> {
 94                 int parent = getParentIndex(index);
 95                 if (parent >= 1 && ((E) elem[index - 1]).compareTo((E) elem[parent - 1]) < 0) {
 96                     swap(index - 1, parent - 1);
 97                     adjust(parent);
 98                 } else if (index <= num / 2) {
 99                     int lchild = getLchildIndex(index);
100                     int rchild = getRchildIndex(index);
101                     if (rchild > num || ((E) elem[lchild - 1]).compareTo((E) elem[rchild - 1]) < 0) {
102                         if (((E) elem[index - 1]).compareTo((E) elem[lchild - 1]) > 0) {
103                             swap(index - 1, lchild - 1);
104                             adjust(lchild);
105                         }
106                     } else {
107                         if (((E) elem[index - 1]).compareTo((E) elem[rchild - 1]) > 0) {
108                             swap(index - 1, rchild - 1);
109                             adjust(rchild);
110                         }
111                     }
112                 }
113             }
114         }
115     }
116 
117     @Override
118     public void set(int index, E e) throws HeapException {
119         checkOutOfBounds(index);
120         elem[index - 1] = e;
121         adjust(index);
122     }
123 
124     @SuppressWarnings("unchecked")
125     @Override
126     public void remove(int index) throws HeapException {
127         checkOutOfBounds(index);
128         if (index < num) set(index, (E) elem[num - 1]);
129         elem[num - 1] = null;
130         num--;
131     }
132 
133     private String toString(int index) {
134         if (index < 1 || index > num || elem[index - 1] == null) return null;
135         String s = elem[index - 1] + "";
136         String ls = toString(getLchildIndex(index));
137         String rs = toString(getRchildIndex(index));
138         if (ls != null || rs != null) s += "[" + (ls == null ? "-" : ls) + ", " + (rs == null ? "-" : rs) + "]";
139         return s;
140     }
141 
142     @Override
143     public String toString() {
144         try {
145             checkEmpty();
146         } catch (HeapException e) {
147             return "该堆为空堆！";
148         }
149         return toString(1);
150     }
151 
152 }

SqHeap

　　链式存储结构如下：

  1 public class LHeap<E extends Comparable<E>> extends AbstractHeap<E> {
  2 
  3     protected enum NodeTag {
  4         ROOT, LEFT, RIGHT;
  5     }
  6 
  7     protected class Node {
  8 
  9         /**
 10          * 元素
 11          */
 12         E elem;
 13 
 14         /**
 15          * 左子结点
 16          */
 17         Node lchild;
 18 
 19         /**
 20          * 右子结点
 21          */
 22         Node rchild;
 23 
 24         /**
 25          * 父结点
 26          */
 27         Node parent;
 28 
 29         /**
 30          * 标志
 31          */
 32         NodeTag tag;
 33 
 34         Node(E elem) {
 35             this.elem = elem;
 36             tag = NodeTag.ROOT;
 37         }
 38 
 39         Node(Node parent, NodeTag tag) {
 40             this.parent = parent;
 41             this.tag = tag;
 42         }
 43 
 44         int getIndex() {
 45             if (tag == NodeTag.ROOT) return 1;
 46             return tag == NodeTag.LEFT ? getLchildIndex(parent.getIndex()) : getRchildIndex(parent.getIndex());
 47         }
 48 
 49     }
 50 
 51     protected Node root;
 52 
 53     public LHeap(Tag tag) {
 54         this.tag = tag;
 55     }
 56 
 57     @SuppressWarnings("unchecked")
 58     public LHeap(Tag tag, E... elems) {
 59         this (tag);
 60         for (E e : elems) add(e);
 61     }
 62 
 63     protected Node getNode(int index) {
 64         if (index == 1) return root;
 65         Node node = getNode(getParentIndex(index));
 66         if (node == null) return null;
 67         return index % 2 == 0 ? node.lchild : node.rchild;
 68     }
 69 
 70     @Override
 71     public void add(E e) {
 72         num++;
 73         if (num == 1) {
 74             root = new Node(e);
 75         } else {
 76             Node parent = getNode(getParentIndex(num));
 77             Node node;
 78             if (num % 2 == 0) {
 79                 node = new Node(parent, NodeTag.LEFT);
 80                 parent.lchild = node;
 81             } else {
 82                 node = new Node(parent, NodeTag.RIGHT);
 83                 parent.rchild = node;
 84             }
 85             while (node.parent != null) {
 86                 if (tag == Tag.GREAT){
 87                     if (e.compareTo(node.parent.elem) > 0) {
 88                         node.elem = node.parent.elem;
 89                         node = node.parent;
 90                     } else {
 91                         break;
 92                     }
 93                 } else {
 94                     if (e.compareTo(node.parent.elem) < 0) {
 95                         node.elem = node.parent.elem;
 96                         node = node.parent;
 97                     } else {
 98                         break;
 99                     }
100                 }
101             }
102             node.elem = e;
103         }
104     }
105 
106     private void swap(Node i, Node j) {
107         E temp = i.elem;
108         i.elem = j.elem;
109         j.elem = temp;
110     }
111 
112     @SuppressWarnings("preview")
113     private void adjust(Node node) {
114         switch (tag) {
115             case GREAT -> {
116                 if (node.parent != null && node.elem.compareTo(node.parent.elem) > 0) {
117                     swap(node, node.parent);
118                     adjust(node.parent);
119                 } else if (node.lchild != null) {
120                     if (node.rchild == null || node.lchild.elem.compareTo(node.rchild.elem) > 0) {
121                         if (node.elem.compareTo(node.lchild.elem) < 0) {
122                             swap(node, node.lchild);
123                             adjust(node.lchild);
124                         }
125                     } else {
126                         if (node.elem.compareTo(node.rchild.elem) < 0) {
127                             swap(node, node.rchild);
128                             adjust(node.rchild);
129                         }
130                     }
131                 }
132             }
133             case LESS -> {
134                 if (node.parent != null && node.elem.compareTo(node.parent.elem) < 0) {
135                     swap(node, node.parent);
136                     adjust(node.parent);
137                 } else if (node.lchild != null) {
138                     if (node.rchild == null || node.lchild.elem.compareTo(node.rchild.elem) < 0) {
139                         if (node.elem.compareTo(node.lchild.elem) > 0) {
140                             swap(node, node.lchild);
141                             adjust(node.lchild);
142                         }
143                     } else {
144                         if (node.elem.compareTo(node.rchild.elem) > 0) {
145                             swap(node, node.rchild);
146                             adjust(node.rchild);
147                         }
148                     }
149                 }
150             }
151         }
152     }
153 
154     @Override
155     public void set(int index, E e) throws HeapException {
156         checkOutOfBounds(index);
157         Node node = getNode(index);
158         node.elem = e;
159         adjust(node);
160     }
161 
162     @Override
163     public void remove(int index) throws HeapException {
164         checkOutOfBounds(index);
165         Node node = getNode(num);
166         if (index < num) set(index, node.elem);
167         if (num == 1) {
168             root = null;
169         } else if (num % 2 == 0) {
170             node.parent.lchild = null;
171         } else {
172             node.parent.rchild = null;
173         }
174         num--;
175     }
176 
177     private String toString(Node node) {
178         String s = "" + node.elem;
179         if (node.lchild != null || node.rchild != null) {
180             s += "[" + (node.lchild == null ? "-" : toString(node.lchild));
181             s += ", " + (node.rchild == null ? "-" : toString(node.rchild)) + "]";
182         }
183         return s;
184     }
185 
186     @Override
187     public String toString() {
188         return toString(root);
189     }
190 
191 }

LHeap