binary heap

Work in Progress

Summary

Binary heap

implements priority queue ADT
semi-sorted “tree”
leverages divide-and-conquer to imitate sorting

Operation	Method	Performance
`enqueue(v)`	insert as a leaf, reheapify	-
`dequeue()`	extract the head	-

Slow build heap

enqueue elements, each

java

for (int i = 0; i < arr.length; i++)
	pq.offer(arr[i]);

Fast build heap

java

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(arr, arr.length)); // supply the array as a collection

Concept

Data structure

abstraction as a complete binary tree

concrete implementation as a compact array, with 1-based indexing

Max/min heap property

the parent of every vertex(except the root) is >= that vertex
every path from node to leaf is a sorted sub-array

Heap traversal

parent(i) = i >> 1 // integer division by 2

left(i) = i << 1 // multiply by 2

right(i) = (i << 1) + 1 // multiply by 2, add 1

hence why we use the 1-based array, reduces computation

TODO: CS1231S
Height of complete binary tree

using bitwise left shift n = 1 << (h + 1)

Heapify

bubbles an element up

Extract max/min

get the highest priority(head)

Application

Kattis: Numbers On a Tree

understanding heap traversal

java

String[] input = br.readLine().split(" ");

int h = Integer.parseInt(input[0]), n = 1 << (h + 1); // height and total number of nodes

int i = 1; // node number, 1-based
if (input.length > 1) { // possible that 
	for (char c : input[1].toCharArray())
		if (c == 'L')
			i <<= 1;
		else {
			i <<= 1;
			i++;
		}
}

pw.println(n - i);

Leetcode: Mice and Cheese

min heap for the opportunity cost

java

PriorityQueue<Integer> pq = new PriorityQueue<>();

int points = 0;
for (int i = 0; i < reward1.length; i++) {
	points += reward2[i];
	pq.add(reward2[i] - reward1[i]);
}

while (k-- > 0) {
	points -= pq.poll();
}

return points;

Leetcode: Find the K-Sum of an Array

min heap for the subtractions
partial sort

java

// test input: [2,4,-2]
// [2] : {2,0}               <- 2nd
//  ├─ [2] : {2,1}           <- 3rd
//  │   ├─ [4] : {4,2}       <- 4th
//  │   └─ [2,4] : {6,2}
//  └─ [2,2] : {4,1}         <- 5th
//      ├─ [2,4] : {6,2}
//      └─ [2,2,4] : {8,2}

long max = 0, minus = 0;
for (int i = 0; i < nums.length; i++) {
	max += Math.max(nums[i], 0); // add +ve numbers to get the max
	nums[i] = Math.abs(nums[i]); // -ve doesn't matter
}

Arrays.sort(nums); // O(n log n)

PriorityQueue<long[]> minheap = new PriorityQueue<>(Comparator.comparingLong(o -> o[0]));
minheap.add(new long[] { nums[0], 0 });

while (--k > 0) { // O(k log k)
	long[] cur = minheap.poll();
	int i = (int) cur[1];
	minus = cur[0];
	if (i < nums.length - 1) {
		// O(log k), add the two next sequences
		minheap.add(new long[] { cur[0] + nums[i + 1], i + 1 });
		minheap.add(new long[] { cur[0] + nums[i + 1] - nums[i], i + 1 });
	}
}

return max - minus;