Here we look at the implementation of Williams' heapsort algorithm in VHDL.
A heap is a data structure organised as a balanced binary tree. Each node in the tree represents an item in the list, and the tree is ordered so that the value of each node is greater than the values of both its children. (Alternatively the ordering could be reversed, so that the value of each node is less than the values of its children.)
A heap can be stored in an array, with the first element containing the root (or parent) of the tree, and subsequent adjacent pairs of elements containing siblings. The array index of the child of a given node is twice the array index of that node, assuming the indices are 1,2,3,...
A heap sort is a software algorithm to sort a list of items. The algorithm is in two parts: first, the list is structured as a heap, and secondly the heap is transformed into an ordered list. One feature of the heap sort algorithm is that no storage additional to the array is required, except when swapping values. The time to complete a sort is of the order Nlog2N, and the algorithm is particularly efficient for partially ordered lists.
HeapSortParallel is a VHDL design entity whose function is to sort a list of integers into a numerically ascending sequence using a heap sort. The unsorted and the sorted lists are input and output in parallel and the algorithm can be represented in pseudo-VHDL as follows:
CreateEmptyHeap;
for EachUnsortedItem loop
InsertIntoHeap;
end loop;
while HeapNotEmpty loop
RemoveBiggestHeapItem;
RemakeHeap;
end loop;
Note that in HeapSortParallel the heap and the unsorted and sorted lists share the same array storage. (Note that you could describe the same algorithm in a software language, such as C or Pascal, in very much the same way.)
A couple of things to try...
- You might want to ponder on why the design entity HeapSortParallel is not synthesizable...
- You might also want to modify the heap sort entity to handle lists of unsorted data of arbitrary length.
You are welcome to use the source code we provide but you must keep the copyright notice with the code (see the Notices page for details).
All of the VHDL required for simulating this model is available on this page.
-- HeapSortParallel
--
-- +-----------------------------+
-- | Copyright 1996 DOULOS |
-- | Library: Sort |
-- | designer : Mike Smith |
-- +-----------------------------+
-- This design contains VHDL'93 code that is incompatible with VHDL'87
library IEEE;
use IEEE.Std_logic_1164.all;
package HeapType is
subtype Key is Integer;
type ListIndex is range 0 to Integer'High;
type List is array (ListIndex range <>) of Key;
end package HeapType;
use Work.HeapType.all;
entity HeapSortParallel is
port (Input: in List;
Output: out List);
end entity HeapSortParallel;
architecture Algorithm of HeapSortParallel is
-- A pure algorithm to input a list of numbers in parallel and output
-- the same values sorted.
procedure Heapify (Heap: inout List; Start: ListIndex) is
-- Percolate item in Start position down into the heap
-- Assumes that the 2 sub-heaps are already valid heaps
-- A heap is a binary tree with Parent > max(Children) at each level
variable Parent: ListIndex := Start;
variable Child: ListIndex := 2*Parent;
variable NewComer: Key := Heap(Start);
begin
while Child <= Heap'Right loop
if Child < Heap'Right then
-- Pick the biggest child...
if Heap(Child + 1) > Heap(Child) then
Child := Child + 1;
end if;
end if;
if Heap(Child) > NewComer then
-- Percolate NewComer down heap
Heap(Parent) := Heap(Child);
Parent := Child;
Child := 2*Parent;
else
exit;
end if;
end loop;
-- Newby has reached his final resting place
Heap(Parent) := NewComer;
end procedure Heapify;
begin
process (Input)
-- Re-define the index constraint so we know for convenience that the
-- first element is numbered 1, and the range is ascending...
variable Heap: List(1 to Input'Length);
variable Biggest: Key;
begin
assert Input'Length = Output'Length
report "HeapSort input and output must be the same length";
Heap := Input;
-- Transform the list into a heap, bottom up...
for J in Heap'Right / 2 downto 1 loop
Heapify(Heap, J);
end loop;
-- Sort the heap into an ascending linear sequence
for J in Heap'Right downto 2 loop
-- Swap the item on the top (the biggest) to the "done" pile...
Biggest := Heap(1);
Heap(1) := Heap(J);
Heap(J) := Biggest;
-- Percolate the promoted item to re-form a valid heap...
Heapify(Heap(1 to J-1), 1);
end loop;
-- Output the heap
Output <= Heap;
end process;
end architecture Algorithm;
To download the VHDL source code, click here.
Back to VHDL models.
