练习 – heap sort

练习 Introduction to Algorithim – heap sort。

其他 sort:https://yanwen.blog/2017/11/01/经典排序算法/

/**
 * heapsort.c
 *
 * @author YanWen <i@yanwen.email>
 * @modified 2018-09-22
 *
 * @NOTE Introduction to Algorithim - heap sort
 */

#include <stdio.h>

#include <stdlib.h>
#include <stdbool.h>

#define _RED(str)   "33[31m" str "33[0m"
#define _GREEN(str) "33[32m" str "33[0m"

#define element_t long long

#define swap(x, y) do {  
  element_t _x = x;      
  element_t _y = y;      
  x = _y;                
  y = _x;                
} while (false)

#define half_round_down(n) ((element_t)(n) / 2)

// ~
// NOTE: indces starts from 0
static element_t parent(const element_t i)
{
  return half_round_down(i - 1);
}

static element_t left(const element_t i)
{
  return (2 * i) + 1;
}

static element_t right(const element_t i)
{
  return (2 * i + 1) + 1;
}
// ~

// O(lgn)
static void max_heapify(element_t * A, const element_t n, const element_t i)
{
  const element_t l = left(i);
  const element_t r = right(i);

  element_t largest = 0;

  largest = (l < n && A[l] > A[i]) ? l : i;
  largest = (r < n && A[r] > A[largest]) ? r : largest;

  if (largest - i)
  {
    swap(A[i], A[largest]);
    max_heapify(A, n, largest);
  }
}

// O(1)
static void build_max_heap(element_t * A, const element_t n)
{
  for (element_t i = half_round_down(n) - 1; i >= 0; i--)
    max_heapify(A, n, i);
}

// O(nlgn)
static void heapsort(element_t * A, const element_t n)
{
  build_max_heap(A, n);
  for (element_t i = n - 1; i > 0; i--)
  {
    swap(A[0], A[i]);
    max_heapify(A, i, 0);
  }
}

static void print(element_t const * A, const element_t n)
{
  for (element_t i = 0; i < n; i++)
    printf(n - i - 1 ? _GREEN("%lld, ") : _GREEN("%lld"), A[i]);
  puts("");
}


int main(int argc, char const *argv[])
{
  const element_t LEN = 9;
  element_t A[] = { -4, 6, 9, 1, 12, -7, 8, 17, -9 };

  print(A, LEN);
  puts(_RED("-> Heap sorting ->"));
  heapsort(A, LEN);
  print(A, LEN);

  return 0;
}

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s