FilesExpand file tree

 master

/

MaxHeap.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

85 lines (72 loc) · 1.74 KB

 master

/

MaxHeap.js

Copy path

Top

File metadata and controls

• Code
• Blame

85 lines (72 loc) · 1.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

/**

* Author: Samarth Jain

* Max Heap implementation in Javascript

*/

class BinaryHeap {

constructor () {

this.heap = []

}

insert (value) {

this.heap.push(value)

this.heapify()

}

size () {

return this.heap.length

}

empty () {

return this.size() === 0

}

// using iterative approach to reorder the heap after insertion

heapify () {

let index = this.size() - 1

while (index > 0) {

const element = this.heap[index]

const parentIndex = Math.floor((index - 1) / 2)

const parent = this.heap[parentIndex]

if (parent[0] >= element[0]) break

this.heap[index] = parent

this.heap[parentIndex] = element

index = parentIndex

}

}

// Extracting the maximum element from the Heap

extractMax () {

const max = this.heap[0]

const tmp = this.heap.pop()

if (!this.empty()) {

this.heap[0] = tmp

this.sinkDown(0)

}

return max

}

// To restore the balance of the heap after extraction.

sinkDown (index) {

const left = 2 * index + 1

const right = 2 * index + 2

let largest = index

const length = this.size()

if (left < length && this.heap[left][0] > this.heap[largest][0]) {

largest = left

}

if (right < length && this.heap[right][0] > this.heap[largest][0]) {

largest = right

}

// swap

if (largest !== index) {

const tmp = this.heap[largest]

this.heap[largest] = this.heap[index]

this.heap[index] = tmp

this.sinkDown(largest)

}

}

}

// Example

// const maxHeap = new BinaryHeap()

// maxHeap.insert([4])

// maxHeap.insert([3])

// maxHeap.insert([6])

// maxHeap.insert([1])

// maxHeap.insert([8])

// maxHeap.insert([2])

// const mx = maxHeap.extractMax()

export { BinaryHeap }