data-structures

MinHeap

Class

class MinHeap {
  key: K;  at(i: number): T;  buildHeap(): void;  decreaseKey(key: S, value: T[S], k: number): T[];  insert(x: T): void;  get(key: S, value: T[S]): T;  readonly length: number;  min(): T;  extractMin(): T;  heapifyUp(i: number): void;  heapify(i: number, start?: number): void;  parent(i: number): number;  left(i: number): number;  right(i: number): number;  sort(): MinHeap<K, T>;  [Symbol.iterator](): Generator<T, void, undefined>;}

Example

[1, 2, 3, 4, 7, 9, 10, 8, 16, 14]

             1
           /  \
          2    3
         / \   / \
        4   7  9  10
       / \  /
      8  16 14

Members

key

K

at

T

@paraminumber

@returnsT

buildHeap

void

Converts A[1…n] to a min heap starts building from n/2

Because elements A[n/2 + 1 … n] are all leaves of the tree 2i > n, for i > n/2 + 1

@complexity

O(n)

Total amount of work in the for loop can be summed as:
- n/4 (1 c) + n/8 (2 c) + n/16 (3 c) + … + 1 (lg n c)
Setting n/4 = 2k and simplifying we get:
- c 2^k ( 1/2^0 + 2/2^1 + 3/2^2 + … (k+1)/2^k )

The term is brackets is bounded by a constant! This means that buildHeap is O(n)

@returnsvoid

decreaseKey

T[]

@paramkeyS

@paramvalueT[S]

@paramknumber

@returnsT[]

insert

void

@paramxT

@returnsvoid

get

T

@complexityO(1)

@paramkeyS

@paramvalueT[S]

@returnsT

length

number

min

T

@returnsT

extractMin

T

@returnsT

heapifyUp

void

@paraminumber

@returnsvoid

heapify

void

correct a single violation of the heap property in a subtree at its root

Assume that the trees rooted at left(i) and right(i) are min-heaps
If element A[i] violates the min-heap property,
- correct violation by “trickling” element A[i] down the tree
- making the subtree rooted at index i a min-heap

@complexity

O(L) for the nodes that are L levels above the leaves

O(1) for time for nodes that are one level above the leaves
O(L) for the nodes that are L levels above the leaves
O(lgn) for root node which is lgn levels above the leaves

@paraminumber

@paramstartnumber

@returnsvoid

parent

number

@complexityO(1)

@paraminumber

@returns

⌊i / 2⌋

left

number

@complexityO(1)

@paraminumber

@returns

2 * i + 1

right

number

@complexityO(1)

@paraminumber

@returns

2 * i + 2

sort

MinHeap<K, T>

@complexity

O(nlogn)

after n iterations the Heap is empty
every iteration involves a swap and a heapify operation
- hence it takes O(logn) time

@returnsMinHeap<K, T>

[Symbol.iterator]

Generator<T, void, undefined>

@returnsGenerator<T, void, undefined>