llheap.cpp

来自「模拟器提供了一个简单易用的平台」· C++ 代码 · 共 87 行

#include <assert.h>
#include "llheap.h"

LLHeap* init_heap (int max_elems)
{
 LLHeap *h = new LLHeap;
 h->max_elems = max_elems;
 h->num_elems = 0;
 h->elem_list = new LLHeapElem [max_elems];
 for (int i = 0; i < max_elems; i++)
   h->elem_list[i].valid = false;
 return h;
}

void delete_heap (LLHeap *h)
{
  delete [] h->elem_list;
  delete h;
  return;
}

void insert (LLHeap *h, int new_val)
{
  assert (h->num_elems < h->max_elems);
  h->elem_list[h->num_elems].valid = true;
  h->elem_list[h->num_elems].value = new_val;
  h->num_elems ++;
  return;
}

// Deletes the min key value. Returns the position where it was
// deleted from in the heap.
int delete_min (LLHeap *h, int &value)
{
  int pos = -1;
  int min_val;

  for (int i = 0; i < h->max_elems; i++)
    {
      if (!(h->elem_list[i].valid))
	continue;
      if (pos == -1)
	{
	  min_val = h->elem_list[i].value;
	  pos = i;
	  continue;
	}

      if (h->elem_list[i].value < min_val)
	{
	  pos = i;
	  min_val = h->elem_list[i].value;
	}
    }

  value = min_val;
  if (pos != -1)
    {
      h->elem_list[pos].valid = false;
      h->num_elems --;
    }
  return pos;
}

void change_key (LLHeap *h, int pos, int new_val)
{
  assert (pos >= 0);
  assert (h->elem_list[pos].valid);
  h->elem_list[pos].value = new_val;
  return;
}

bool heap_check_valid (LLHeap *h, int index)
{
  assert (index < h->max_elems);
  return h->elem_list[index].valid;
}

bool is_empty (LLHeap *h)
{
  return (h->num_elems == 0);
}