JAVA:实现MaxHeap最大堆算法(附完整源码)

package com.thealgorithms.datastructures.heaps;

import java.util.ArrayList;
import java.util.List;

/**
 * Heap tree where a node's key is higher than or equal to its parent's and
 * lower than or equal to its children's.
 *
 */
public class MaxHeap implements Heap {

    private final List<HeapElement> maxHeap;

    public MaxHeap(List<HeapElement> listElements) {
        maxHeap = new ArrayList<>();
        for (HeapElement heapElement : listElements) {
            if (heapElement != null) {
                insertElement(heapElement);
            } else {
                System.out.println("Null element. Not added to heap");
            }
        }
        if (maxHeap.size() == 0) {
            System.out.println("No element has been added, empty heap.");
        }
    }

    /**
     * Get the element at a given index. The key for the list is equal to index
     * value - 1
     *
     * @param elementIndex index
     * @return heapElement
     */
    public HeapElement getElement(int elementIndex) {
        if ((elementIndex <= 0) || (elementIndex > maxHeap.size())) {
            throw new IndexOutOfBoundsException("Index out of heap range");
        }
        return maxHeap.get(elementIndex - 1);
    }

    // Get the key of the element at a given index
    private double getElementKey(int elementIndex) {
        if ((elementIndex <= 0) || (elementIndex > maxHeap.size())) {
            throw new IndexOutOfBoundsException("Index out of heap range");
        }
        
        return maxHeap.get(elementIndex - 1).getKey();
    }

    // Swaps two elements in the heap
    private void swap(int index1, int index2) {
        HeapElement temporaryElement = maxHeap.get(index1 - 1);
        maxHeap.set(index1 - 1, maxHeap.get(index2 - 1));
        maxHeap.set(index2 - 1, temporaryElement);
    }

    // Toggle an element up to its right place as long as its key is lower than its parent's
    private void toggleUp(int elementIndex) {
        double key = maxHeap.get(elementIndex - 1).getKey();
        while (getElementKey((int) Math.floor(elementIndex / 2.0)) < key) {
            swap(elementIndex, (int) Math.floor(elementIndex / 2.0));
            elementIndex = (int) Math.floor(elementIndex / 2.0);
        }
    }

    // Toggle an element down to its right place as long as its key is higher
    // than any of its children's
    private void toggleDown(int elementIndex) {
        double key = maxHeap.get(elementIndex - 1).getKey();
        boolean wrongOrder
                = (key < getElementKey(elementIndex * 2))
                || (key < getElementKey(Math.min(elementIndex * 2, maxHeap.size())));
        while ((2 * elementIndex <= maxHeap.size()) && wrongOrder) {
            // Check whether it shall swap the element with its left child or its right one if any.
            if ((2 * elementIndex < maxHeap.size())
                    && (getElementKey(elementIndex * 2 + 1) > getElementKey(elementIndex * 2))) {
                swap(elementIndex, 2 * elementIndex + 1);
                elementIndex = 2 * elementIndex + 1;
            } else {
                swap(elementIndex, 2 * elementIndex);
                elementIndex = 2 * elementIndex;
            }
            wrongOrder
                    = (key < getElementKey(elementIndex * 2))
                    || (key < getElementKey(Math.min(elementIndex * 2, maxHeap.size())));
        }
    }

    private HeapElement extractMax() {
        HeapElement result = maxHeap.get(0);
        deleteElement(0);
        return result;
    }

    @Override
    public void insertElement(HeapElement element) {
        maxHeap.add(element);
        toggleUp(maxHeap.size());
    }

    @Override
    public void deleteElement(int elementIndex) {
        if (maxHeap.isEmpty())
      try {
            throw new EmptyHeapException("Attempt to delete an element from an empty heap");
        } catch (EmptyHeapException e) {
            e.printStackTrace();
        }
        if ((elementIndex > maxHeap.size()) || (elementIndex <= 0)) {
            throw new IndexOutOfBoundsException("Index out of heap range");
        }
        // The last element in heap replaces the one to be deleted
        maxHeap.set(elementIndex - 1, getElement(maxHeap.size()));
        maxHeap.remove(maxHeap.size());
        // Shall the new element be moved up...
        if (getElementKey(elementIndex) > getElementKey((int) Math.floor(elementIndex / 2.0))) {
            toggleUp(elementIndex);
        } // ... or down ?
        else if (((2 * elementIndex <= maxHeap.size())
                && (getElementKey(elementIndex) < getElementKey(elementIndex * 2)))
                || ((2 * elementIndex < maxHeap.size())
                && (getElementKey(elementIndex) < getElementKey(elementIndex * 2)))) {
            toggleDown(elementIndex);
        }
    }

    @Override
    public HeapElement getElement() throws EmptyHeapException {
        try {
            return extractMax();
        } catch (Exception e) {
            throw new EmptyHeapException("Heap is empty. Error retrieving element");
        }
    }
}

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