Book Image

Haskell Data Analysis cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis cookbook

By: Nishant Shukla

Overview of this book

Step-by-step recipes filled with practical code samples and engaging examples demonstrate Haskell in practice, and then the concepts behind the code. This book shows functional developers and analysts how to leverage their existing knowledge of Haskell specifically for high-quality data analysis. A good understanding of data sets and functional programming is assumed.
Table of Contents (14 chapters)
13
Index

Implementing a min-heap data structure


A heap is a binary tree with both a shape property and a heap property. The shape property enforces the tree to behave in a balanced way by defining each node to have two children unless the node is in the very last level. The heap property ensures that each node is less than or equal to either of its child nodes if it is a min-heap, and vice versa in case of a max-heap.

Heaps are used for constant time lookups for maximum or minimum elements. We will use a heap in the next recipe to implement our own Huffman tree.

Getting started

Install the lens library for easy data manipulation:

$ cabal install lens

How to do it...

  1. Define the MinHeap module in a file MinHeap.hs:

    module MinHeap (empty, insert, deleteMin, weights) where
    
    import Control.Lens (element, set)
    import Data.Maybe (isJust, fromJust)
  2. We will use a list to represent a binary tree data structure for demonstration purposes only. It is best to implement the heap as an actual binary tree (as we have...