CS 131 LECTURE 12 - HEAPS AND HASH TABLES

Terminology:

Full Binary Tree: A Tree Of Depth n Is A Binary Tree With The Maximum Number Of Nodes (2ⁿ - 1)

Level Order Enumeration: Enumeration Of A Binary Tree Is A Numbering Of Each Level From Left To Right, And The Levels From Top To Bottom

Complete Binary Tree

: A Binary Tree, Whose n Nodes, When Enumerated In Level Order, Correspond To The First n Nodes Of The Full Binary Tree Of The Same Depth

Level Order Enumeration Of A Full Binary Tree3 Levels, 7 Nodes (23 - 1 = 7)

Level Order Enumeration Of A Complete Binary Tree

Location Functions For A Complete Binary Tree With n Nodes

Terminology:

Height-Balanced(n) Tree: An Empty Tree Or A Tree With The Following Properties:
1. The Absolute Difference Between The Height Of The Left And Right Subtrees Is Less Than Or Equal To n

2. Both Subtrees Are Height-Balanced(n)

AVL Tree: A Tree That Is Height-Balanced(1)

Important Point:

1. Keeping A Tree Balanced Ensures That There Is A Logarithmic Relationship Between The Height Of The Tree And The Number Of Nodes

Terminology:

Heap: A Complete Binary Tree Each Of Whose Nodes Is Greater Than Or Equal To All Its Children

Maximum Branch: The Maximum Branch Of A Heap Is The Branch Along Which The Data Value In Each Node Is Greater Than Or Equal To The Data Value Of Its Sibling

Graphic Representation:

GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS PRIVATE;
  TYPE Heaps IS ARRAY(Integer RANGE <>) OF
    Elements;
  WITH FUNCTION Get_Key(Element: Elements)
   RETURN Keys;
  WITH FUNCTION "<"(Left,Right: Keys) RETURN
    Boolean IS <>;
PROCEDURE Sift(Heap: IN OUT Heaps);
PROCEDURE Sift(Heap: IN OUT Heaps) IS
  Root: Elements := Heap(Heap'First);
  Node: Integer := Heap'First * 2;
BEGIN
  WHILE Node <= Heap'Last LOOP
    IF Node < Heap'Last AND THEN
      Get_Key(Heap(Node)) <
      Get_Key(Heap(Node + 1)) THEN
        Node := Node + 1;
    END IF;
    EXIT WHEN
      Get_Key(Heap(Node)) < Get_Key(Root);
    Heap(Node / 2) := Heap(Node);
    Node := Node * 2;
  END LOOP;
  Heap(Node / 2) := Root;
END Sift;

Priority Queue Package Body

WITH Sift;
PACKAGE BODY Priority_Queue_Package IS
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements) IS
  BEGIN
    IF Queue.Highest = Size THEN
      RAISE Full_Queue;
    END IF;
    Queue.Highest := Queue.Highest + 1;
    Queue.List(Queue.Highest) := Item;
    --Heap_Up(Queue); Not Included
  END Enqueue;
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements) IS
    PROCEDURE Heap_Down IS NEW Sift
      (Elements,Priorities,Lists,Get_Rank);
  BEGIN
    IF Queue.Highest = 0 THEN
      RAISE Empty_Queue;
    END IF;
    Item := Queue.List(1);
    Queue.List(1) :=
      Queue.List(Queue.Highest);
    Queue.Highest := Queue.Highest - 1;
    Heap_Down(Queue.List(1..Queue.Highest));
  END Dequeue;
END Priority_Queue_Package;

Terminology:

Hash Function: A Function That Maps A Relatively Large Domain Into A Relatively Small Co-domain

Major Types Of Hash Functions

1. Mod Hash Function
Table Size Should Be A Value With No Prime Factors Less Than 20

2. Digit Selection

Requires Careful Digit Selection

3. Folding

Qualities Of A Good Hash Function

1. Easy & Quick To Compute

2. Even Distribution

Collision Resolution Techniques

1. Linear Probing (Creates Clustering)

2. Quadratic Probing

3. External Chaining

4. Coalesced Chaining

Hash Table Package Specification

WITH Linked_List_Package;
GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS (<>);
  WITH FUNCTION Get_Key(Element: Elements)
    RETURN Keys;
  WITH PROCEDURE Put(Item: IN Elements);
PACKAGE Hash_Table_Package IS
  TYPE Tables IS LIMITED PRIVATE;
  PROCEDURE Insert(Table: IN OUT Tables;
    Element: IN Elements);
  PROCEDURE Delete(Table: IN OUT Tables;
    Key: IN Keys);
  PROCEDURE Find(Table: IN Tables;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean);
  Full_Table,Duplicate_Key: EXCEPTION;
PRIVATE
  Prime_Size: CONSTANT := 997;
  PACKAGE LL IS NEW Linked_List_Package
    (Elements);
  USE LL;
  TYPE Tables IS ARRAY(1..Prime_Size) OF
    Lists;
END Hash_Table_Package;

Hash Table Package Body

PACKAGE BODY Hash_Table_Package IS
  FUNCTION Hash(Key: IN Keys) RETURN
    Positive IS
  BEGIN
    RETURN Keys'Pos(Key) MOD Prime_Size;
  END Hash;
  PROCEDURE Search(Table: IN Tables;
    Key: IN Keys; Location: OUT LL.Lists;
    Found: OUT Boolean) IS SEPARATE;
  PROCEDURE Find(Table: IN Tables;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean) IS SEPARATE;
  PROCEDURE Insert(Table: IN OUT Tables;
    Element: IN Elements) IS SEPARATE;
  PROCEDURE Delete(Table: IN OUT Tables;
    Key: IN Keys) IS SEPARATE;
END Hash_Table_Package;

Important Points:

1. This Package Uses A Hash Table Which Is An Array Of Linked Lists

2. This Package Uses The Simplest Hash Function, The Modulo Hash Function

3. This Package Resolves Collisions Using The Chaining Technique

Search And Find Procedures

SEPARATE (Hash_Table_Package)
PROCEDURE Search(Table: IN Tables;
  Key: IN Keys; Location: OUT LL.Lists;
  Found: OUT Boolean) IS
  Last,This: Lists;
BEGIN
  This := Table(Hash(Key));
  WHILE This /= NULL LOOP
    EXIT WHEN Key = Get_Key(This.Data);
    Last := This;
    This := This.Next;
  END LOOP;
  Found := This /= NULL;
  Location := Last;
END Search;
SEPARATE (Hash_Table_Package)
PROCEDURE Find(Table: IN Tables;
  Key: IN Keys; Element: OUT Elements;
  Found: OUT Boolean) IS
  Location: Lists; In_Table: Boolean;
BEGIN
  Search(Table,Key,Location,In_Table);
  IF In_Table THEN
    Element := Location.Next.Data;
  END IF;
  Found := In_Table;
END Find;

Insert And Delete Procedures

SEPARATE (Hash_Table_Package)
PROCEDURE Insert(Table: IN OUT Tables;
  Element: IN Elements) IS
  Key: Keys := Get_Key(Element);
  Location,List: Lists;
  Found: Boolean;
BEGIN
  Search(Table,Key,Location,Found);
  IF Found THEN RAISE Duplicate_Key; END IF;
  List := Table(Hash(Key));
  LL.Insert(List,Location, Element);
EXCEPTION
  WHEN Storage_Error => RAISE Full_Table;
END Insert;
SEPARATE (Hash_Table_Package)
PROCEDURE Delete(Table: IN OUT Tables;
  Key: IN Keys) IS
  Location,List: Lists;
  Found: Boolean;
BEGIN
  Search(Table,Key,Location,Found);
  List := Table(Hash(Key));
  IF Found THEN
    LL.Delete(List,Location);
  END IF;
END Delete;

String Hash Function

GENERIC
  Prime: IN Positive;
  Bytes: IN Positive;
FUNCTION String_Hash(A_String: IN String)
  RETURN Natural;
FUNCTION String_Hash(A_String: IN String)
  RETURN Natural IS
  Hash: Natural := 0;
  Power: Natural;
BEGIN
  FOR I IN A_String'Range LOOP
    Power := 128 ** ((I - 1) MOD Bytes);
    Hash := Hash + 
      Character'Pos(A_String(I)) * Power;
  END LOOP;
  RETURN Hash MOD Prime;
END String_Hash;

Important Points:

1. The Bytes Generic Constant Allows Groups Of Characters To Be Numerically Concatenated And Then Summed

2. More Complicated Algorithms Can Be Developed Using Exclusive Or

Sequential Sorted List

Advantage
O(log2n) Binary Search Possible

Disadvantage

O(n) Insertion And Deletion

Linked Sorted List

Advantage
O(1) Insertion And Deletion (Excluding Search)

Disadvantage

O(n) Search Required

Binary Search Tree

Advantage
O(log2n) Search, Insertion And Deletion

Disadvantage

Complicated Algorithms Required For Height Balancing

Hash Table

Advantage
O(1) Search, Insertion And Deletion

Disadvantage

Key Type Must Be Discrete