- 技术
- Heap
package treeplay
.heap
;
import java
.util
.Arrays
;
public class Heap {
private final int[] items
= new int[10];
private int size
;
public void insert(int value
) {
if (isFull()) {
throw new IllegalStateException("the heap is full");
}
items
[size
++] = value
;
bubbleUp();
}
public boolean isFull() {
return size
== items
.length
;
}
public int remove() {
if (isEmpty()) {
throw new IllegalStateException("The heap is Empty");
}
var t
= items
[0];
items
[0] = items
[--size
];
bubbleDown();
return t
;
}
private void bubbleDown() {
var index
= 0;
while (index
<= size
&& !isValidParent(index
)) {
var largerChild
= largerChildIndex(index
);
swap(index
, largerChild
);
index
= largerChild
;
}
}
public boolean isEmpty() {
return size
== 0;
}
private int largerChildIndex(int index
) {
if (!hasLeftChild(index
)) {
return index
;
}
if (!hasRightChild(index
)) {
return leftChildIndex(index
);
}
return (leftChild(index
) > rightChild(index
)) ?
leftChildIndex(index
) : rightChildIndex(index
);
}
private boolean isValidParent(int index
) {
if (!hasLeftChild(index
)) {
return true;
}
var isValid
= items
[index
] >= leftChild(index
);
if (hasRightChild(index
)) {
isValid
&= items
[index
] >= rightChild(index
);
}
return isValid
;
}
private int leftChildIndex(int index
) {
return 2 * index
+ 1;
}
private int rightChildIndex(int index
) {
return 2 * index
+ 2;
}
private int leftChild(int index
) {
return items
[leftChildIndex(index
)];
}
private int rightChild(int index
) {
return items
[rightChildIndex(index
)];
}
private boolean hasLeftChild(int index
) {
return leftChildIndex(index
) <= size
;
}
private boolean hasRightChild(int index
) {
return rightChildIndex(index
) <= size
;
}
private void bubbleUp() {
var index
= size
- 1;
var parentIndex
= parent(index
);
while (index
> 0 && items
[index
] > items
[parentIndex
]) {
swap(index
, parentIndex
);
index
= parentIndex
;
}
}
private void swap(int first
, int second
) {
var temp
= items
[first
];
items
[first
] = items
[second
];
items
[second
] = temp
;
}
private int parent(int index
) {
return (index
- 1) / 2;
}
@Override
public String
toString() {
return Arrays
.toString(Arrays
.copyOf(items
, size
));
}
public int max() {
if (isEmpty()) throw new IllegalStateException();
return items
[0];
}
public int getKthLargest(int k
) {
if (k
< 1 || k
> size
) throw new IllegalStateException();
for (var i
= 0; i
< k
- 1; i
++) {
remove();
}
return max();
}
}
package treeplay
.heap
;
public class HeapUtil {
public static void heapify(int[] arr
) {
for (var i
= arr
.length
/ 2 - 1; i
>= 0; --i
) {
heapify(arr
, i
);
}
}
private static void heapify(int[] a
, int index
) {
var larger
= index
;
var leftIndex
= 2 * index
+ 1;
var rightIndex
= 2 * index
+ 2;
if (leftIndex
< a
.length
&& a
[leftIndex
] > a
[larger
]) {
larger
= leftIndex
;
}
if (rightIndex
< a
.length
&& a
[rightIndex
] > a
[larger
]) {
larger
= rightIndex
;
}
if (index
== larger
) return;
swap(a
, index
, larger
);
heapify(a
, larger
);
}
private static void swap(int[] a
, int l
, int r
) {
var t
= a
[l
];
a
[l
] = a
[r
];
a
[r
] = t
;
}
}
Processed:
0.008, SQL:
9
