基于 堆二叉树 实现 优先队列

二叉堆(满足一些特殊性质的二叉树)

• 二叉堆是一颗完全二叉树
• 满二叉树:节点是固定的(第一层 1个 第二层2个 第三层 4个。。。) 每个非叶子节点都有2个孩子。

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 
1
2
3
4
5

• 完全二叉树:从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 
1
2
3
4
5
6
7

• 二叉堆(完全二叉树):每个父节点值大于等于其所有孩子节点的值(最大堆)

           62
       /       \  
     41         30  
    /  \        /  \
  28    16    22   13
 /  \   /
19   17  15 
1
2
3
4
5
6
7

用数组存储二叉堆

按照二叉树的 结构存储数组 插入新数组的时候只要计算 他的父节点
(父节点计算公式为 i/2 i为当前数组索引 ) 如果插入元素比父节点小 则 成功 如果父节点 较小 则互相调换值 然后 在判断 当前位置的父节点 是否 比新插入的元素小 如果小交换 反复重复这个过程直到 插入元素 比 父节点小

从堆中取出最大元素

如果从堆中 取出最大值 62 后需要把堆中最后一个元素取出 替代 取出的位置 然后为了满足 二叉堆的性质 需要从子节点中选择最大的节点 替换直到满足 父节点小于子节点的性质。

Heapify

将任意数组整理成堆的形状

从最后一个 节点计算 找到父亲节点(n-1/2) 如果父节点小于子节点 执行交换 重复这个操作直到父节点大于子节点。

Array.java

public class Array<E> {
    private E[] data;
    private int size;

    /**
     *
     * @param capacity 构造函数,传入数组的容量capacity 构造Array
     */
    public Array(int capacity){
        data =(E[])new Object[capacity];
        size = 0;

    }
    public int getSize(){
        return size;
    }
    public int  getCapacity(){
        return  data.length;
    }
    //无参数构造函数,默认数组的容量 capacity =10
    public void addLast(E e){
        add(size,e);
    }
    public void addFirst(E e){
        add(0,e);
    }
    public Array(){
        this(10);
    }
    public void add(int index,E e){
        if(size > (int)(data.length) * 2/3)
            //System.out.println(2 * data.length);
            resize((int)(data.length) * 4/3);
        if(index < 0 || index>size)
            throw  new IllegalArgumentException("Addlast failed.index must over zero and index must small than size");
        for (int i = size;i >= index;i--)
            data[i + 1]= data[i];
        data[index] = e;
        size ++;
    }

    /**
     *
     * @param index 要删除的索引
     * @return 返回删除的值
     */
    public E remove(int index){
        if(index >size || index<0 )
            throw new IllegalArgumentException("Delval failed.index must big than zeor and index not over than size");
        E ret =data[index];
        for(int i=index ;i<size;i++){
            data[i] =data[i+1];
        }
        data[size] = null; //loitering objects != memory leak
        size--;
        if(size <= (int)data.length/3 && data.length/3 != 0)
            resize((int)data.length * 2/3);
        return ret;
    }

    /**
     *
     * @return 删除以一个值返回删除的元素
     */
    public E removeFirst(){
        E ret ;
        ret = this.remove(0);
        return ret;
    }

    /**
     *
     * @return 删除最后一个值返回删除的元素
     */
    public E removeLast(){
        E ret ;
        ret = this.remove(size);
        return ret;
    }

    /**
     *
     * @return 删除元素
     */
    public void removeElement(E e){
        int find =find(e);
        if(find != -1){
             remove(find);
        }


    }
    public boolean isEmpty(){
        if(data.length == 0)
            return true;
        else
            return false;

    }
    public E getFirst(){
        return get(0);

    }
    public E getLast(){
        return get(size - 1);

    }

    /**
     *
     * @param index 传入一个不超过当前数组size的索引
     * @return 返回索引相对应的值
     */
    E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed ,index is Illegal");
        return data[index] ;
    }

    /**
     *
     * @param index 传入一个不超过数组size的索引
     * @param e 传入值
     */
    void set(int index,E e){
        if(index >size || index < 0)
            throw  new IllegalArgumentException("Set failed ,index is overflow");
        data[index] =e;

    }

    /**
     *
     * @param e 传入元素的值查找
     * @return 找到返回真
     */
    public boolean contains(E e){
        for(int i = 0 ;i<size;i++){
            if(data[i] == e){
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @param e  要查找的参数
     * @return 查找参数找到返回1 没找到返回-1
     */
    public int find(E e){
        for (int i =0 ;i<size;i++){
            if(data[i] .equals(e))
                return i;
        }
        return -1;

    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array :size= %d ,capacity =%d\n ", size, data.length ));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1) {
                res.append(",");
            }else
            {
                res.append(']');
            }
        }
        return res.toString();
    }
    public void resize(int newCapacity){

        E[] newE = (E[]) new Object[newCapacity];
        for(int i =0;i<size;i++){
            newE[i] =data[i];

        }
        data =newE;


    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

MaxHeap.java

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data = new Array<>();
    }
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i =parent(arr.length-1);i>=0;i--)
            siftDown(i);
    }
    //返回堆中的元素个数
    public int size(){
        return data.getSize();
    }
    //返回一个布尔值,表示堆中是否为空
    public boolean isEmpty(){
      return data.isEmpty();
    }
    //返回完全二叉树组中,一个缩影表示的元素的父节点的索引。
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index zero has no parent");
        return(index -1)/2;
    }
    //返回完全二叉树的数组表示中,一个索引所表示的元素的有孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

    private int leftChild(int index){
        return index * 2 + 1;
    }

    //对堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() -1);

    }
    //交换最大值
    private void siftUp(int i) {
        //和父节点比大小 如果父节点小就交换
        while(i > 0 && data.get(parent(i)).compareTo(data.get(i))<0){
            //交换父节点和子节点
            data.swap(i,parent(i));
            //重新获得交换后插入值的索引
            i = parent(i);
        }
    }
    public E findMax(){
        if(data.getSize() == 0)
            throw  new IllegalArgumentException("cannot find Max When Heap is empty");
        return data.get(0);
    }

    //取出堆中最大元素
    public E extractMax(){
        E ret =findMax();
        data.swap(0,data.getSize() -1);
        data.removeLast();
        siftDown(0);
        return ret;
    }


    private void siftDown(int i) {
      while (leftChild(i) <data.getSize()){
          int j = leftChild(i);
          if(j+1 <data.getSize() && data.get(j+1).compareTo(data.get(j))>0)
              j ++ ;
          if(data.get(i).compareTo(data.get(j))>=0)
              break;
          data.swap(i,j);
          i=j;
      }
    }
    //替换节点
    public E replace(E e){
        E ret =findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }


  



}

Queue.java
```java
public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

优先队列
PriorityQueue.java

public class PriorityQueue <E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;
    public PriorityQueue(){
        maxHeap =new MaxHeap<>();
    }
    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.findMax();
    }

    @Override
    public E getFront() {
        return maxHeap.extractMax();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

使用Heapify 将直接生成的数组 传入 算法复杂度为 On(logn)
使用add 一个个添加元素 算法复杂度为O(n)

import java.util.Random;

public class Main {

    private static double testHeap(Integer[] testData, boolean isHeapify){

        long startTime = System.nanoTime();

        MaxHeap<Integer> maxHeap;
        if(isHeapify)
            maxHeap = new MaxHeap<>(testData);
        else{
            maxHeap = new MaxHeap<>();
            for(int num: testData)
                maxHeap.add(num);
        }

        int[] arr = new int[testData.length];
        for(int i = 0 ; i < testData.length ; i ++)
            arr[i] = maxHeap.extractMax();

        for(int i = 1 ; i < testData.length ; i ++)
            if(arr[i-1] < arr[i])
                throw new IllegalArgumentException("Error");
        System.out.println("Test MaxHeap completed.");

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int n = 1000000;

        Random random = new Random();
        Integer[] testData = new Integer[n];
        for(int i = 0 ; i < n ; i ++)
            testData[i] = random.nextInt(Integer.MAX_VALUE);

        double time1 = testHeap(testData, false);
        System.out.println("Without heapify: " + time1 + " s");

        double time2 = testHeap(testData, true);
        System.out.println("With heapify: " + time2 + " s");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

插入100万 随机数 性能 如上。