com.alexprut.algo.datastructures

Class BinaryHeap

java.lang.Object

com.alexprut.algo.datastructures.BinaryHeap

Direct Known Subclasses:

MaxHeap, MinHeap

public abstract class BinaryHeap
extends java.lang.Object

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	elements
protected int	size

Constructor Summary

Constructors

Constructor and Description
BinaryHeap(int[] elements)

Method Summary

Modifier and Type	Method and Description
void	build() Time complexity: O(n)
int[]	elements()
int	extract() Time complexity: O(logn)
abstract void	heapify(int i) Time complexity: O(logn)
void	heapsort() Time complexity: O(nlogn) Space complexity: algorithms is in-place
abstract void	insert(int e) Time complexity: O(logn)
static int	left(int i) Time complexity: Θ(1)
static int	parent(int i) Time complexity: Θ(1)
static int	right(int i) Time complexity: Θ(1)
int	root() Time complexity: Θ(1)
int	size() Time complexity: Θ(1)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

elements

protected int[] elements

size

protected int size

Constructor Detail

BinaryHeap

public BinaryHeap(int[] elements)

Method Detail

parent

public static int parent(int i)

Time complexity: Θ(1)

left

public static int left(int i)

Time complexity: Θ(1)

right

public static int right(int i)

Time complexity: Θ(1)

root

public int root()

Time complexity: Θ(1)

extract

public int extract()
            throws java.lang.Exception

Time complexity: O(logn)

Throws:

java.lang.Exception

heapify

public abstract void heapify(int i)

Time complexity: O(logn)

build

public void build()

Time complexity: O(n)

insert

public abstract void insert(int e)

Time complexity: O(logn)

size

public int size()

Time complexity: Θ(1)

elements

public int[] elements()

heapsort

public void heapsort()

Time complexity: O(nlogn) Space complexity: algorithms is in-place