Tag Archives: data structures

Heaps or priority queues in Java Script

Leave a reply

Still work in progress …

 

Part I Heapify …

 

heap-sorting

 

Part II sort and heapify

We start swapping values and heapify each time starting from 0 to the length of i

function heapSort(arr) {

    function maxHeapify(arr, i, N) {
        var leftChild = i * 2 + 1;
        var rightChild = i * 2 + 2;
        var largest = i;
    
        if(leftChild < N && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
    
        if(rightChild < N && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
    
        if(largest != i) {
            var temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            maxHeapify(arr, largest, N);
        }
    }
    
    // CREATE A HEAP
    for(var i = parseInt(arr.length / 2 - 1); i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
    
    console.log("heap represented in array: ", arr);
    
    // SORT THE ARRAY
    for(var i =  arr.length - 1; i >= 0; i --) {
        var temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
    
        maxHeapify(arr, 0, i);
    }
}

const arr = [4, 6, 3, 2, 9, 1];
heapSort(arr);

console.log("sorted array:", arr);

 

Linked Lists

Leave a reply

Linked list

Singly-linked list example implementation in Java Script

Let’s store these values from the diagram above in linked list.

Using Object:

const list = {
    head: {
        value: 20,
        next: {
            value: 18,
            next: {
                value: 15,
                next: {
                    value: 67,
                    next: null
                }
            }
        }
    }
};


/* example of retrieving the value at second position */

console.log(list.head.next); // the result should be 18

 

Using class

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var linkList = new ListNode(20);
linkList.next = new ListNode(18);
linkList.next.next = new ListNode(15);
linkList.next.next.next = new ListNode(67);
linkList.next.next.next.next = null;

/* example of retrieving the last value */
console.log(linkList.next.next.next); // the result should be 67

 

Traversing double linked list example

var list  = {
  one: {value: 1, prev: null, next: null},
  two: {value: 2, prev: null, next: null},
  three: {value: 3, prev: null, next: null}
}

var root = list.one;

list.one.next = list.two;
list.two.prev = list.one;
list.two.next = list.three;
list.three.prev = list.two;

var i = 0;

var element = root;
var loop = true;

while(loop == true) {
  console.log(">>", element.value);
  if(element.next == null)
      loop = false;
  element = element.next;
}