Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

A heap implementation supporting deletion

2017-11-14

Idea

Recently, I was doing a project needing a heap structure, i.e. use it to store fringe nodes in Dijstra. The difference between it and a typical heap is that I may need to delete inside elements in this heap. So I made one instead of using PriorityQueue. The idea is to assign every element an ID. The heap class consists of a position array and a data array. Position array records the position of a given ID in the data array.

I initially tried to use generic type directly for the implementation. But I didn’t figure out how to get the id of a generic-type element. Finally, I decided to create a HeapNode class as the element type in heap and use wrapper for different real data type.

Interface

package heap;

public interface Heap<T> {

    void insert(T node);

    T poll();

    void delete(T node);

    T peek();

    boolean isEmpty();
}

HeapNode

package heap;

public class HeapNode<T> {
    public int id;
    public int val;
    public T data;
    public HeapNode(int id, int val, T data) {
        this.id = id;
        this.val = val;
        this.data = data;
    }
}

Implementation

package heap;

import java.util.Arrays;

public class MyHeapImpl {
    private int lastIndex;
    private int[] posArray;
    private HeapNode[] dataArray;

    public MyHeapImpl(int size) {
        lastIndex = 0;
        posArray = new int[size];
        Arrays.fill(posArray, -1);
        dataArray = new HeapNode[size];
    }

    public boolean isEmpty() {
        return lastIndex == 0;
    }

    public HeapNode peek() {
        if (isEmpty()) {
            return null;
        }
        return dataArray[0];
    }

    public HeapNode poll() {
        if (isEmpty()) {
            return null;
        }
        HeapNode ans = peek();
        delete(ans);
        return ans;
    }

    public void insert(HeapNode node) {
        dataArray[lastIndex] = node;
        posArray[node.id] = lastIndex;
        swimUp(lastIndex);
        lastIndex++;
    }

    public boolean delete(HeapNode node) {
        int pos = posArray[node.id];
        if (pos < 0) {
            return false;
        }
        // fix corner case, the one to delete is the last one
        if (pos == lastIndex - 1) {
            posArray[node.id] = -1;
            dataArray[pos] = null;
            lastIndex--;
            return true;
        }
        dataArray[pos] = dataArray[lastIndex - 1];
        posArray[dataArray[pos].id] = pos;
        dataArray[lastIndex - 1] = null;
        lastIndex--;
        if (pos != 0 && dataArray[pos].val > dataArray[(pos-1) / 2].val) {
            swimUp(pos);
        } else {
            sinkDown(pos);
        }
        return true;
    }

    private void swimUp(int pos) {
        if (pos == 0 || dataArray[pos].val <= dataArray[(pos-1) / 2].val) {
            return;
        }
        swap(pos, (pos-1) / 2);
        swimUp((pos-1) / 2);

    }

    private void sinkDown(int pos) {
        int maxChildPos;
        if (2 * pos + 1 >= lastIndex) {
            return;
        }
        if (2 * pos + 2 >= lastIndex) {
            maxChildPos = 2 * pos + 1;
        } else {
            maxChildPos = (dataArray[2 * pos + 1].val > dataArray[2 * pos + 2].val) ?
                    2 * pos + 1 : 2 * pos + 2;
        }
        if (dataArray[maxChildPos].val <= dataArray[pos].val) {
            return;
        }
        swap(pos, maxChildPos);
        sinkDown(maxChildPos);
    }
    // need to update pos
    private void swap(int pos1, int pos2) {
        HeapNode tmp = dataArray[pos1];
        dataArray[pos1] = dataArray[pos2];
        posArray[dataArray[pos1].id] = pos1;
        dataArray[pos2] = tmp;
        posArray[dataArray[pos2].id] = pos2;
    }

    public static void main(String[] args) {
        MyHeapImpl test = new MyHeapImpl(100);
        for (int i = 0; i < 5; i++) {
            test.insert(new HeapNode<Integer>(i,i+1,i+1));
        }
        test.insert(new HeapNode<Integer>(5,9,9));
        System.out.println(test.poll().val);
        System.out.println(test.poll().val);
        test.insert(new HeapNode<Integer>(5,9,9));
        System.out.println(test.poll().val);
        while (!test.isEmpty()) {
            System.out.println(test.poll().val);
        }
    }
}

An example of wrapper class

In this case, we can see I wrapped a class GraphNode to HeapNode, thus the heap works for it.

package heap;

import graph.GraphNode;

public class GraphNodeHeap implements Heap<GraphNode>{

    private MyHeapImpl myHeap;

    public GraphNodeHeap(int size) {
        this.myHeap = new MyHeapImpl(size);
    }

    @Override
    public void insert(GraphNode node) {
        HeapNode<GraphNode> heapNode = new HeapNode<>(node.getId(), node.getBandwidth(), node);
        myHeap.insert(heapNode);
    }

    @Override
    public void delete(GraphNode node) {
        HeapNode<GraphNode> heapNode = new HeapNode<>(node.getId(), node.getBandwidth(), node);
        myHeap.delete(heapNode);
    }

    @Override
    public boolean isEmpty() {
        return myHeap.isEmpty();
    }

    @Override
    public GraphNode poll() {
        HeapNode heapNode = myHeap.poll();
        return (GraphNode) heapNode.data;
    }

    @Override
    public GraphNode peek() {
        HeapNode heapNode = myHeap.peek();
        return (GraphNode) heapNode.data;
    }

    public static void main(String[] args) {
        Heap<GraphNode> test = new GraphNodeHeap(5);
        GraphNode node = new GraphNode(0);
        node.setBandwidth(1);
        test.insert(node);
        System.out.println(test.poll().getId());
    }
}

GraphNode class

package graph;

import java.util.HashSet;
import java.util.Set;


public class GraphNode {
    private final int id;
    private Set<Edge> edges;
    private GraphNode prev;
    private Status status;
    private int bandwidth;

    public GraphNode(int id) {
        this.id = id;
        this.edges = new HashSet<>();
        this.status = Status.UNSEEN;
    }

    public int getId() {
        return this.id;
    }

    public boolean addEdge(int edgeId, GraphNode n, int weight) {
        return this.edges.add(new Edge(edgeId, this, n, weight));
    }

    public Set<Edge> getNeighbors() {
        return this.edges;
    }

    public GraphNode getPrev() {
        return prev;
    }

    public void setPrev(GraphNode prev) {
        this.prev = prev;
    }

    public Status getStatus() {
        return status;
    }

    public void setStatus(Status status) {
        this.status = status;
    }

    public void setBandwidth(int bandwidth) {
        this.bandwidth = bandwidth;
    }

    public int getBandwidth() {
        return this.bandwidth;
    }
}

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.