Heap sort on C++ and on Haskell

gistfile1.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

class binheap {
    std::size_t heap_size;

    static std::size_t heap_parent (std::size_t i) {
        return i / 2;
    }

    /* For left & right, note that arrays are 0-based */
    static std::size_t heap_left (std::size_t i) {
        return 2*(i + 1) - 1;
    }

    static std::size_t heap_right (std::size_t i) {
        return 2*(i + 1);
    }

    template<typename Iterator>
    void max_heapify (Iterator begin, std::size_t i) {
        std::size_t l  = heap_left (i);
        std::size_t r  = heap_right (i);
        std::size_t largest = i;

        if (l < heap_size && *(begin + l) > *(begin + i)) {
            largest = l;
        }
        if (r < heap_size && *(begin + r) > *(begin + largest)) {
            largest = r;
        }
        if (largest != i) {
            std::swap (*(begin + i), *(begin + largest));
            max_heapify (begin, largest);
        }
    }

public:
    template<typename Iterator>
    binheap (Iterator begin, Iterator end)
    : heap_size (std::distance (begin, end)) {
        if (heap_size <= 1) {
            return;
        }
        
        /* build max heap */
        for (std::size_t i = heap_size / 2 - 1;; i--) {
            max_heapify (begin, i);
            if (i == 0) {
                break;
            }
        }
        /* heap sort itself */
        for (std::size_t i = heap_size - 1; i > 0; i--) {
            std::swap (*begin, *(begin + i));
            heap_size -= 1;
            max_heapify (begin, 0);
        }
    }
};

int main (int argc, char *argv[]) {
    std::vector<int> v = {33, 77, 23, 12, 0, 21};
    binheap (v.begin(), v.end());
    std::for_each (v.begin(), v.end(), [](int i) { std::cout << i << ' '; });
    std::cout << std::endl;
    return 0;
}

gistfile2.hs

{-# LANGUAGE ScopedTypeVariables #-}

module HeapSort where

import Control.Monad (when, forM_)
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
    
heapSort :: forall a . Ord a => [a] -> [a]
heapSort as = runST $ do
    let size = length as
    ar <- newListArray (1, size) as :: ST s (STArray s Int a)
    hs <- newSTRef size
    buildHeap size ar size
    sortHeap hs ar size
    getElems ar
  where    
    heapLeft  i = 2*i
    heapRight i = 2*i + 1

    maxHeapify hs arr i = do
      v <- readArray arr i
      let l = heapLeft i
          r = heapRight i
      largest <- newSTRef i
    
      when (l < hs) $ do
        lv <- readArray arr l
        when (lv > v) $ writeSTRef largest l
    
      when (r < hs) $ do
        rv <- readArray arr r
        ll <- readSTRef largest >>= readArray arr
        when (rv > ll) $ writeSTRef largest r
    
      readSTRef largest >>= \lg -> when (lg /= i) $ do
        readArray arr lg >>= writeArray arr i
        writeArray arr lg v
        maxHeapify hs arr lg
    
    buildHeap hs arr size = do
      let i = size `div` 2
      forM_ [i, pred i .. 1] $ \j -> do
        maxHeapify hs arr j

    sortHeap heapSize arr size = do
      hs <- readSTRef heapSize
      forM_ [hs, pred hs .. 2] $ \i -> do
        t <- readArray arr i
        readArray arr 1 >>= writeArray arr i
        writeArray arr 1 t
        modifySTRef heapSize pred
        readSTRef heapSize >>= \h -> maxHeapify h arr 1