[go: up one dir, main page]
Scribd
Upload
59 views2 pages

Solution

The document contains a Java implementation of a Power of Two Max Heap data structure. It includes methods for inserting values, popping the maximum value, and maintaining the heap property through heapify operations. The constructor enforces a minimum branching factor of 2 for the heap.

Uploaded by

22tec2ee011
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views2 pages

Solution

The document contains a Java implementation of a Power of Two Max Heap data structure. It includes methods for inserting values, popping the maximum value, and maintaining the heap property through heapify operations. The constructor enforces a minimum branching factor of 2 for the heap.

Uploaded by

22tec2ee011
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

import java.util.

ArrayList;​
import java.util.List;​
​
public class PowerOfTwoMaxHeap {​
​
private final int branchingFactor;​
private List<Integer> heap;​
​
public PowerOfTwoMaxHeap(int branchingFactor) {​
if (branchingFactor < 2) {​
throw new IllegalArgumentException("Branching factor must
be at least 2");​
}​
this.branchingFactor = branchingFactor;​
this.heap = new ArrayList<>();​
}​
​
private int parent(int i) {​
return (i - 1) / branchingFactor;​
}​
​
private int leftChild(int i) {​
return i * branchingFactor + 1;​
}​
​
private int rightChild(int i) {​
return i * branchingFactor + 2;​
}​
​
private void swap(int i, int j) {​
int temp = heap.get(i);​
heap.set(i, heap.get(j));​
heap.set(j, temp);​
}​
​
private void heapifyDown(int i) {​
int largest = i;​
int left = leftChild(i);​
int right = rightChild(i);​
​
if (left < heap.size() && heap.get(left) > heap.get(largest))
{​
largest = left;​
}​
​
if (right < heap.size() && heap.get(right) >
heap.get(largest)) {​
largest = right;​
}​
​
if (largest != i) {​
swap(i, largest);​
heapifyDown(largest);​
}​
}​
​
private void heapifyUp(int i) {​
while (i > 0 && heap.get(i) > heap.get(parent(i))) {​
swap(i, parent(i));​
i = parent(i);​
}​
}​
​
public void insert(int value) {​
heap.add(value);​
heapifyUp(heap.size() - 1);​
}​
​
public int popMax() {​
if (heap.isEmpty()) {​
throw new IllegalStateException("Heap is empty");​
}​
​
int max = heap.get(0);​
swap(0, heap.size() - 1);​
heap.remove(heap.size() - 1);​
heapifyDown(0);​
​
return max;​
}​
}​

You might also like