DATS 2300202011

Prev Up Next

Denne uken skal vi gå gjennom heap som datastruktur og heapsortering. Vi går også gjennom huffmantrær og hvordan vi kan bruke prefix-koder for å komprimere data tapsløst. 

Heap datastruktur

I denne videoen går vi gjennom heap som datastruktur og hvordan et komplett minimumstre kan brukes til sortering. Et minimumstre har alle foreldrenoder mindre eller lik verdi som sine barnenoder. En minimumsheap er i tillegg ett komplett tre. Dette gjør at vi enkelt kan lagre det som et array ved å bruke node-id som index i arrayet. 

Heapsort i kildekode

I denne videoen går vi gjennom hvordan vi kan skrive heapsortering i kildekode. Så lenge man lager en algoritme som gjør de nødvendige byttene så er dette relativt greit. Det vanskeligste er kanskje å lage stopp-kriterier for iterasjon. Kildekoden ligger som vanlig på github.

 

Huffman-trær og komprimering

I denne forelesningen så går vi gjennom hvordan vi kan komprimere data ved å bruke Huffmans metode for å lage optimale bit-koder. Jeg har også tidligere laget et slideset som går gjennom noe av det vi tar opp på forelesning, og hvis du er interessert kan du se på hvordan man kjører bit-koding i C++ i et prosjekt jeg har på github.