heap_t

HW 0x4.1: Due Fri, 08 Aug

Review Show

Goal: Implement an data structure based sorting algorithm.

On Due Dates

• I am not allowed to make assignments due during finals.
• However, I am supportive of “no excuse” late turn-ins up until the final project is due.

• This is the first of two “data structures” assignments, implementing the “Merkle tree” of blockchain.
• The data stored by the structure is untyped and the heap is provided only with its size.
  • The same is true of the provided comparison function.
• It is split over 3 files:
  • tester.c which is an example of how some client could use heap_t
  • heap_t.h which the public API you will implement, as with list_t
    • You may not change any lines and must use the array implementation.
    • This is learning objective of the assignment.
  • heap_t.c where you have some freedom but will be implementing known algorithms.
  • Additionally, a Makefile is provided.

heap_t Show

Initialize or construct a new heap.

• You may not change the type but may change the names.
• Implement a max heap, wherein the maximum element per the comparison function called gt below is in the initial position.
• You may 1-index or 0-index.

heap_t heap(size_t ele_size, bool (*gt)(void *, void *));

• I stack allocated my heap, which are welcome but not required to do.
• My initial heap explicitly contained zero elements.

The Heap Struct

• I am requiring the usage of a single internal array, a function pointer, and something to track the size of elements in the array.
• You do not have to maintain capacity and there is no graceful way to avoiding maintaining num_eles (though non-graceful is fine) but it is probably easier to view them as required.

#include <stdbool.h>

typedef struct heap_struct {
    /* These may be changed, but probably are okay */
    size_t ele_size; /* size of element */
    size_t num_eles; /* number of elements */
    size_t capacity; /* current capacity of the heap */
    bool (*gt)(void *, void *); /* for "greater than" */
    /* You must store all data elements s.t. reachable from 1 pointer */
    void *eles;
} heap_t;

Explanation

• ele_size
  • This heap implementation allows storage of elements of any size_t specifiable size.
  • For example, it could store hash digests, 4096_t, fixed length strengths, or uint24_t’s.
  • This is a helpful exercise in reflecting on types and sizes.
• num_eles
  • A heap must track its size to know where to place the next element on an insert operation.
• capacity
  • You are not required to keep an internal array precisely large enough to store all elements.
  • I only change the size of my internal array by doubling, a common rule of thumb.
  • You can change the size of an array with novel malloc, a memcpy, and a free, or
  • You can change the size of an array with realloc, which is preferred but was not covered in lecture.
  • You are not required to have a distinct num_eles and capacity, but are sufficiently encouraged to do so I made both fields mandatory.
• gt
  • This is just the comparison function, without which the sorting regime of the heap is unclear and should be maintained within the data structure.
  • I separately wanted you to see a struct with a function in it!
• eles
  • This is the entries of the heap.
  • It must satisfy the heap property of the element at the initial location being the maximum.
  • All elements must be stored linearly in a single contigious memory block.
  • You may index to zero 0 or one 1 at your discretion, I used zero indexing which seemed unexpectedly easier when writing the code.

insert Show

Insert an element

void insert(heap_t *heap, void *ele_ptr);

• Given the pointer to some element of appropriate size to be stored in the heap, place it in the first available location in the heap array then perform the heapify operation.
• Consult the slides if you are unclear on what heapify is.

maxpop Show

Pop the maximal element

void *maxpop(heap_t *heap);

• This returns a heap allocated copy of the former maximum value in the heap.
• Separately, these element is removed from the heap.
• Finally, the heap is rearranged to maintain the heap property using a “SiftDown” operation.

Sift Down

• After a maxpop, the initial index - zero or one - is vacant.
• Overwrite this value at this location with the last element in the heap array - the rightmost leaf in the last layer.
• Compare this value, now at the initial position, which each of its children.
• Swap it with the greatest of its children.
• Continue to swap, or “sift down”, this value until it is either in a leaf position or is greater than both of its children.

Visual Demo

• Begin with the default heap.

{224, 160, 192, 64, 96, 128}

• Heap allocate a space for 224 to be returned to the client (and freed by the client).
• Overwrite 224 with the rightmost leaf of the final layer.
  • In this case, I also just leave this value in the array (why not?)
  • I just won’t look at it due to it being outside of the number of elements, and it will be freed eventually.

{128, 160, 192, 64, 96}

• I check both of 128s children, find the maximum, and compare that to 128
  • The maximum is 192
  • That is greater than 128
  • So, swap.

{192, 160, 128, 64, 96}

• If 128 had child nodes, I would recurse, but in the case the process terminates here as the 128 is a leaf.
• We notice that the heap property is satisfied - all parent nodes are greater than all of their child nodes.

Tester Show

Novel Tester

• Versus other testers this term, I wanted to provide a more concrete file that actually used the heap_t, performed operations, and issued outputs as print statements.
• I hope that tester is self-documenting, but would love to hear your questions!

• For reference, here is heap_t.h