Skip to content

Instantly share code, notes, and snippets.

@beyond-code-github
Created April 17, 2024 08:45
Show Gist options
  • Save beyond-code-github/22e2d5eebf8a24cdf1a327f65886aaee to your computer and use it in GitHub Desktop.
Save beyond-code-github/22e2d5eebf8a24cdf1a327f65886aaee to your computer and use it in GitHub Desktop.
Basic Trie implementation and problem solve with Heap - Javascript
"use strict";
const Heap = require("heap");
class Trie {
count = 0;
key = null;
// each node stores a map to its child nodes
character = {};
insert(key) {
let curr = this;
for (const c of key) {
curr.character[c] = curr.character[c] || new Trie();
curr = curr.character[c];
}
curr.key = key;
curr.count++;
}
preorder (heap) {
if (this.count > 0) {
heap.push({key: this.key, count: this.count})
}
for (const c of Object.values(this.character)) {
c.preorder(heap);
}
}
}
const keys = ["code", "coder", "coding", "codable", "codec", "codecs", "coded", "codeless", "codec", "codecs", "codependence", "codex", "codify", "codependents", "codes", "code", "coder", "codesign", "codec", "codeveloper", "codrive", "codec", "codecs", "codiscovered"];
const trie = new Trie();
for (const key of keys) {
trie.insert(key);
}
const heap = new Heap((a, b) => b.count - a.count);
trie.preorder(heap);
console.log(heap)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment