Tech Tips: March 2020

Summary

This post covers development of a Priority Queue with Typescript. The queue is implemented via a Binary Heap. Typescript features such as static type-checking and object-oriented concepts such as classes, interfaces and inheritance are utilized.

Design

Implementation

Queue Item Class

 export class Item {
    priority:number;
    value:object;

    constructor(priority:number, value:object) {
        this.priority = priority;
        this.value = value;
    }
 }

Heap Interface

import {Item} from './item';

export enum Order {MIN, MAX};
export interface Heap {
    insert(item:Item):void;
    extract():Item;
    peek():Item;
    show():void;
    size():number;
};

Binary Heap Class - snippets

export class BinaryHeap implements Heap {
    private order:Order;
    private heap:Item[];

    insert(item:Item):void {
        this.heap.push(item);
        this.siftUp(this.heap.length-1);
    };

    private siftUp(idx:number):void {
        let parent:number;
        let sorted:boolean = false;

        while (!sorted) {
          parent = this.getParent(idx)
          switch (this.order) {
              case Order.MIN: {
                if (this.heap[idx].priority < this.heap[parent].priority) {
                    this.swap(idx, parent);
                    idx = parent;
                }
                else {
                    sorted = true;
                }
                break;
              }
              case Order.MAX: {
                if (this.heap[idx].priority > this.heap[parent].priority) {
                    this.swap(idx, parent);
                    idx = parent;
                }
                else {
                    sorted = true;
                }
                break;
              }
              default: {
                  sorted = true;
                  break;
              }
          }  
        }
    }

Priority Queue Class

export class PriorityQueue {
    heap:BinaryHeap;

    constructor(items:Item[]){
        this.heap = new BinaryHeap(items);
    }

    insert(item:Item):void {
        this.heap.insert(item);
    }

    isEmpty():boolean {
        return this.heap.size() == 0;
    }

    peek():Item {
        return this.heap.peek();
    }

    pull():Item {
        return this.heap.extract();
    }

    show():void {
        this.heap.show();
    }
}

Example

Source

https://github.com/joeywhelan/PriorityQueue

Sunday, March 29, 2020

Priority Queue with Typescript