This repository was archived by the owner on Oct 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 178
Expand file tree
/
Copy pathMaxHeap.java
More file actions
115 lines (85 loc) · 2.45 KB
/
MaxHeap.java
File metadata and controls
115 lines (85 loc) · 2.45 KB
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
import javafx.util.Pair;
import java.util.ArrayList;
public class MaxHeap <T extends Comparable <T>> {
private ArrayList <T> heap;
public MaxHeap() {
heap = new ArrayList <T>( 32 );
heap.add( null );
}
private MaxHeap( T[] array ) {
heap = new ArrayList <T>( 2 );
heap.add( null );
if ( array == null || array.length < 1 ) {
return;
}
heap.ensureCapacity( array.length + 2 );
for ( int i = 0; i < array.length; ++i ) {
heap.add( array[ i ] );
}
for ( int i = ( heap.size() ) / 2; i >= 1; --i ) {
bubbleDown( i );
}
}
public void insert( T element ) {
heap.add( element );
bubbleUp( heap.size() - 1 );
}
public boolean isEmpty() {
return ( heap.size() <= 1 );
}
public T getMax() throws EmptyHeapException {
if ( heap.size() <= 1 ) {
throw new EmptyHeapException( "getMax" );
}
return heap.get( 1 );
}
public void extractMax() throws EmptyHeapException {
if ( heap.size() <= 1 ) {
throw new EmptyHeapException( "extractMax" );
}
heap.set( 1, heap.get( heap.size() - 1 ) );
heap.remove( heap.size() - 1 );
bubbleDown( 1 );
}
public static <E extends Comparable <E>> MaxHeap <E> makeHeap( E[] array ) {
return new MaxHeap <E>( array );
}
private void bubbleUp( int n ) {
if ( n > 1 ) {
T parent = heap.get( n >> 1 );
if ( parent.compareTo( heap.get( n ) ) == -1 ) {
heap.set( n >> 1, heap.get( n ) );
heap.set( n, parent );
bubbleUp( n >> 1 );
}
}
}
private void bubbleDown( int n ) {
if ( ( ( n << 1 ) + 1 ) < heap.size() || ( n << 1 ) < heap.size() ) {
Pair <Integer, T> son = getSonWithUpperKey( n );
if ( son.getValue().compareTo( heap.get( n ) ) == 1 ) {
heap.set( son.getKey(), heap.get( n ) );
heap.set( n, son.getValue() );
bubbleDown( son.getKey() );
}
}
}
private Pair <Integer, T> getSonWithUpperKey( int n ) {
int leftSonIndex = n << 1;
int rightSonIndex = leftSonIndex + 1;
if ( rightSonIndex >= heap.size() ) {
return new Pair <Integer, T>( leftSonIndex, heap.get( leftSonIndex ) );
}
T leftSon = heap.get( leftSonIndex );
T rightSon = heap.get( rightSonIndex );
if ( leftSon.compareTo( rightSon ) > 0 ) {
return new Pair <Integer, T>( leftSonIndex, leftSon );
}
return new Pair <Integer, T>( rightSonIndex, rightSon );
}
}
class EmptyHeapException extends Exception {
public EmptyHeapException( String action ) {
super( "Heap is empty. Cannot perform action '".concat( action ).concat( "'." ) );
}
}