Dia 56/2019 - Estruturas de dados em JS: heap

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 56, mostrando o uso do Heap.

Código

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};

const defaultCompare = (a, b) => {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

const reverseCompare = compareFn => (a, b) => compareFn(b, a);

const swap = (array, a, b) => {
[array[a], array[b]] = [array[b], array[a]];
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class MinHeap {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
this.heap = [];
}

getLeftIndex(index) {
return (2 * index) + 1;
}

getRightIndex(index) {
return (2 * index) + 2;
}

getParentIndex(index) {
if (index === 0) {
return undefined;
}
return Math.floor((index - 1) / 2);
}

size() {
return this.heap.length;
}

isEmpty() {
return this.size() <= 0;
}

clear() {
this.heap = [];
}

findMinimum() {
return this.isEmpty() ? undefined : this.heap[0];
}

insert(value) {
if (value != null) {
const index = this.heap.length;
this.heap.push(value);
this.siftUp(index);
return true;
}
return false;
}

siftDown(index) {
let element = index;
const left = this.getLeftIndex(index);
const right = this.getRightIndex(index);
const size = this.size();
if (
left < size
&& this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
) {
element = left;
}
if (
right < size
&& this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
) {
element = right;
}
if (index !== element) {
swap(this.heap, index, element);
this.siftDown(element);
}
}

siftUp(index) {
let parent = this.getParentIndex(index);
while (
index > 0
&& this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
) {
swap(this.heap, parent, index);
index = parent;
parent = this.getParentIndex(index);
}
}

extract() {
if (this.isEmpty()) {
return undefined;
}
if (this.size() === 1) {
return this.heap.shift();
}
const removedValue = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return removedValue;
}

heapify(array) {
if (array) {
this.heap = array;
}
const maxIndex = Math.floor(this.size() / 2) - 1;
for (let i = 0; i <= maxIndex; i++) {
this.siftDown(i);
}
return this.heap;
}

getAsArray() {
return this.heap;
}
}

class MaxHeap extends MinHeap {
constructor(compareFn = defaultCompare) {
super(compareFn);
this.compareFn = compareFn;
this.compareFn = reverseCompare(compareFn);
}
}
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
/*
* MinHeap
***********************************/
let heap = new MinHeap();

heap.insert(2);
heap.insert(3);
heap.insert(4);
heap.insert(5);

heap.insert(2);

console.log(heap.getAsArray());
// [2, 2, 4, 5, 3]
console.log(heap.size());
// 5
console.log(heap.isEmpty());
// false
console.log(heap.findMinimum());
// 2

heap = new MinHeap();
for (let i = 1; i < 10; i++) {
heap.insert(i);
}

console.log(heap.getAsArray());
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(heap.extract());
// 1
console.log(heap.getAsArray());
// [2, 4, 3, 8, 5, 6, 7, 9]

/*
* MaxHeap
***********************************/
const maxHeap = new MaxHeap();

maxHeap.insert(2);
maxHeap.insert(3);
maxHeap.insert(4);
maxHeap.insert(5);

maxHeap.insert(1);

console.log(maxHeap.getAsArray(), ' <<<<<<');
// [5, 4, 3, 2, 1]
console.log(maxHeap.size());
// 5
console.log(maxHeap.isEmpty());
// false
console.log(maxHeap.findMinimum());
// 5

maxHeap.insert(6);
maxHeap.insert(9);
maxHeap.insert(10);
maxHeap.insert(14);

console.log(maxHeap.getAsArray());
// [14, 10, 6, 9, 1, 3, 5, 2, 4]
console.log(maxHeap.extract());
// 14
console.log(maxHeap.getAsArray());
// [10, 9, 6, 4, 1, 3, 5, 2]

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.