JetBrains Academy: Binary heap in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Simple heap:
You are given queries of the following types:
+ aadds an element «a» to the heap;-removes the minimum element from the heap;?prints the current depth of the heap.
Clarification: There will be no removal queries when the heap is empty.
Input: In the first line is n, that is the number of queries. The following n lines contain the queries in the ways mentioned above.
Output: For each depth query print out the current heap’s depth on the new line.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
MinBinaryHeap myHeap = new MinBinaryHeap(lines);
for (int i = 0; i < lines; i++) {
String commandLine = scanner.nextLine();
InputUtils.executeOperations(commandLine, myHeap);
}
}
}class InputUtils {
/**
* Method reads array of arguments, firs of which should be command to execute, latter - element;
* Then it passes matched command to method run for execution along with rest of arguments.
*
* @param commandLine - command line of Strings containing command, element (or just command)
* @param heap - on which matched command will be executed
*/
public static void executeOperations(String commandLine, MinBinaryHeap heap) {
String[] arguments = commandLine.split("\\s+");
String command = arguments[0];
Command cmd = Command.getCommandFor(command);
run(Objects.requireNonNull(cmd), heap, arguments);
}
/**
* Method runs the apply method from enum for provided command
*
* @param command to be executed
* @param heap on which we execute the command
* @param arguments to use with the command: key, value
*/
private static void run(Command command, MinBinaryHeap heap, String... arguments) {
command.apply(heap, arguments);
}
}enum Command {
INSERT("+") {
@Override
public void apply(MinBinaryHeap heap, String... arguments) {
int element = Integer.parseInt(arguments[1]);
heap.insert(element);
}
}, EXTRACT_MIN("-") {
@Override
public void apply(MinBinaryHeap heap, String... arguments) {
heap.extractMin();
}
}, CHECK_HEAP_DEPTH("?") {
@Override
public void apply(MinBinaryHeap heap, String... arguments) {
System.out.println(heap.depth());
}
};
private final String command;
Command(String command) {
this.command = command;
}
/**
*
* @param symbol of command
* @return Command object which value matches provided symbol
* @throws IllegalArgumentException when no symbol matches are found
*/
public static Command getCommandFor(String symbol) {
for (Command name : values()) {
if (name.command.equals(symbol)) {
return name;
}
}
throw new IllegalArgumentException("Wrong symbol provided: " + symbol + "\n" +
"Please use following: + / - / ?");
}
/**
*
* @param heap to be modified by Command object
* @param arguments command + element to be added or just command
*/
public abstract void apply(MinBinaryHeap heap, String... arguments);
}class MinBinaryHeap {
private final int maxSize;
private int size;
private final int[] heap;
public MinBinaryHeap(int maxSize) {
this.maxSize = maxSize;
this.size = 0;
heap = new int[this.maxSize + 1];
heap[0] = Integer.MIN_VALUE;
}
public boolean isEmpty() {
return size == 0;
}
public int depth() {
int depth = 0;
for (int i = size; i > 1; i = i / 2) {
depth++;
}
return depth;
}
public void insert(int element) throws Overflow {
int index = ++size;
if (size > maxSize) {
throw new Overflow();
}
this.heap[index] = element;
while (heap[index] < heap[index / 2]) {
swap(index, index / 2);
index = index / 2;
}
}
public int extractMin() {
if (isEmpty()) {
throw new NoSuchElementException("No elements in the heap");
}
int popped = heap[1];
heap[1] = heap[size--];
minHeapify(1);
return popped;
}
public void convertToMinHeap() {
for (int pos = size / 2; pos >= 1; pos--) {
minHeapify(pos);
}
}
private void swap(int fpos, int spos) {
int tmp = heap[fpos];
heap[fpos] = heap[spos];
heap[spos] = tmp;
}
/**
* Method is based on the principle that there is a convenient way of storing binary trees in arrays;
* where children of the node i will be nodes numbered 2i and 2i+1.
*
* @param pos - position of node i in the array
*/
private void minHeapify(int pos) {
// if pos is in the middle of the heap array
if (2 * pos == size) {
// if element at the pos i is greater than the element at 2i
if (heap[pos] > heap[2 * pos]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
}
return;
}
// if pos is in the first half of the heap array
if (2 * pos <= size) {
// if element at the pos i is greater than the element at 2i or 2i+1
if (heap[pos] > heap[2 * pos] || heap[pos] > heap[2 * pos + 1]) {
// if 21 element is smaller, than it is selected to be swapped with i element on pos index
if (heap[2 * pos] < heap[2 * pos + 1]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
} else {
swap(pos, 2 * pos + 1);
minHeapify(2 * pos + 1);
}
}
}
}
static class Overflow extends ArrayIndexOutOfBoundsException {
Overflow() {
System.out.println("Heap overflow");
}
}
}Swaps:
Numbers from 1 to n are added to minHeap in a certain order. For each number find out how many times it changed its position in the minHeap. Presume that you use the code that was given in the first part of the lesson.
Clarification: for addition use method insert(), add nodes in the same order as they are in the input.
Input: In the first line is the number n. In the second line, divided by spaces, are n numbers from 1 to n.
Output: n numbers divided by spaces: i-th number indicates the number of position changes of the number i in the constructed minHeap.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
MinBinaryHeap myHeap = new MinBinaryHeap(size);
for (int i = 0; i < size; i++) {
myHeap.insert(scanner.nextInt());
}
int[] swaps = myHeap.countSwaps();
for (int i = 0; i < size; i++) {
System.out.print(swaps[i] + " ");
}
}
}class MinBinaryHeap {
private final int maxSize;
private int size;
private final int[] heap;
private final int[] swaps;
public MinBinaryHeap(int maxSize) {
this.maxSize = maxSize;
this.size = 0;
heap = new int[this.maxSize + 1];
swaps = new int[this.maxSize];
heap[0] = Integer.MIN_VALUE;
}
public boolean isEmpty() {
return size == 0;
}
public int depth() {
int depth = 0;
for (int i = size; i > 1; i = i / 2) {
depth++;
}
return depth;
}
public int[] countSwaps() {
// sorting swaps in ascending order:
Map<Integer, Integer> elementSwaps = new TreeMap<>();
for (int i = 1; i <= size; i++) {
elementSwaps.put(this.heap[i], this.swaps[i - 1]);
}
// getting sorted array of swaps from values of the map
Collection<Integer> swapCounts = elementSwaps.values();
return swapCounts.stream().mapToInt(x -> x).toArray();
}
public void insert(int element) throws Overflow {
int index = ++size;
if (size > maxSize) {
throw new Overflow();
}
this.heap[index] = element;
while (heap[index] < heap[index / 2]) {
swap(index, index / 2);
index = index / 2;
}
}
public int extractMin() {
if (isEmpty()) {
throw new NoSuchElementException("No elements in the heap");
}
int popped = heap[1];
heap[1] = heap[size--];
minHeapify(1);
return popped;
}
public void convertToMinHeap() {
for (int pos = size / 2; pos >= 1; pos--) {
minHeapify(pos);
}
}
private void swap(int fpos, int spos) {
int tmp = heap[fpos];
heap[fpos] = heap[spos];
heap[spos] = tmp;
// swaps counter:
int tmpS = swaps[fpos - 1];
swaps[fpos - 1] = swaps[spos - 1] + 1;
swaps[spos - 1] = tmpS + 1;
}
/**
* Method is based on the principle that there is a convenient way of storing binary trees in arrays;
* where children of the node i will be nodes numbered 2i and 2i+1.
*
* @param pos - position of node i in the array
*/
private void minHeapify(int pos) {
// if pos is in the middle of the heap array
if (2 * pos == size) {
// if element at the pos i is greater than the element at 2i
if (heap[pos] > heap[2 * pos]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
}
return;
}
// if pos is in the first half of the heap array
if (2 * pos <= size) {
// if element at the pos i is greater than the element at 2i or 2i+1
if (heap[pos] > heap[2 * pos] || heap[pos] > heap[2 * pos + 1]) {
// if 21 element is smaller, than it is selected to be swapped with i element on pos index
if (heap[2 * pos] < heap[2 * pos + 1]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
} else {
swap(pos, 2 * pos + 1);
minHeapify(2 * pos + 1);
}
}
}
}
static class Overflow extends ArrayIndexOutOfBoundsException {
Overflow() {
System.out.println("Heap overflow");
}
}
}Sort with States:
You're given an array of elements. Your task is to sort it in ascending order using a binary heap. Print not only the sorted array but also the initial state of the heap and its states after extracting every element.
Input: The first line contains N, that is the length of the array. In the next line, there are elements of the array. These are the integers that don't exceed 109 in absolute value (1 ≤ N ≤ 100).
Output: In the first line print the heap that was constructed after calling minHeap(), and in the following N – 1 lines print heap states after removing the next element. In the last (N + 1) line print the sorted array.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
final int size = scanner.nextInt();
int[] array = new int[size];
int[] sorted = new int[size];
for (int i = 0; i < size; i++) {
array[i] = scanner.nextInt();
}
MinBinaryHeap myHeap = MinBinaryHeap.fromArray(array);
System.out.println(myHeap);
for (int i = 0; i < size; i++) {
sorted[i] = myHeap.extractMin();
System.out.print(myHeap);
if (myHeap.size() == 0) {
for (int j = 0; j < size; j++) {
System.out.print(sorted[j] + " ");
}
}
System.out.println();
}
}
}class MinBinaryHeap {
private final int maxSize;
private int size;
public int[] heap;
private final int[] swaps;
private MinBinaryHeap(int[] array) {
this.maxSize = array.length;
this.size = array.length;
this.heap = new int[this.maxSize + 1];
this.swaps = new int[this.maxSize];
heap[0] = Integer.MIN_VALUE;
System.arraycopy(array, 0, this.heap, 1, array.length);
}
public static MinBinaryHeap fromArray(int[] array) {
MinBinaryHeap heap = new MinBinaryHeap(array);
heap.convertToMinHeap();
return heap;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public int[] countSwaps() {
// sorting swaps in ascending order:
Map<Integer, Integer> elementSwaps = new TreeMap<>();
for (int i = 1; i <= size; i++) {
elementSwaps.put(this.heap[i], this.swaps[i - 1]);
}
// getting sorted array of swaps from values of the map
Collection<Integer> swapCounts = elementSwaps.values();
return swapCounts.stream().mapToInt(x -> x).toArray();
}
public void insert(int element) throws Overflow {
int index = ++size;
if (size > maxSize) {
throw new Overflow();
}
this.heap[index] = element;
while (heap[index] < heap[index / 2]) {
swap(index, index / 2);
index = index / 2;
}
}
public int extractMin() {
if (isEmpty()) {
throw new NoSuchElementException("No elements in the heap");
}
int popped = heap[1];
heap[1] = heap[size--];
minHeapify(1);
return popped;
}
public void convertToMinHeap() {
for (int pos = size / 2; pos >= 1; pos--) {
minHeapify(pos);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= size; i++) {
sb.append(this.heap[i]).append(" ");
}
return sb.toString().trim();
}
private void swap(int fpos, int spos) {
int tmp = heap[fpos];
heap[fpos] = heap[spos];
heap[spos] = tmp;
// swaps counter:
int tmpS = swaps[fpos - 1];
swaps[fpos - 1] = swaps[spos - 1] + 1;
swaps[spos - 1] = tmpS + 1;
}
/**
* Method is based on the principle that there is a convenient way of storing binary trees in arrays;
* where children of the node i will be nodes numbered 2i and 2i+1.
*
* @param pos - position of node i in the array
*/
private void minHeapify(int pos) {
// if pos is in the middle of the heap array
if (2 * pos == size) {
// if element at the pos i is greater than the element at 2i
if (heap[pos] > heap[2 * pos]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
}
return;
}
// if pos is in the first half of the heap array
if (2 * pos <= size) {
// if element at the pos i is greater than the element at 2i or 2i+1
if (heap[pos] > heap[2 * pos] || heap[pos] > heap[2 * pos + 1]) {
// if 21 element is smaller, than it is selected to be swapped with i element on pos index
if (heap[2 * pos] < heap[2 * pos + 1]) {
swap(pos, 2 * pos);
minHeapify(2 * pos);
} else {
swap(pos, 2 * pos + 1);
minHeapify(2 * pos + 1);
}
}
}
}
static class Overflow extends ArrayIndexOutOfBoundsException {
Overflow() {
System.out.println("Heap overflow");
}
}
}