File: heap.hh

package info (click to toggle)
bliss 0.73-4
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 712 kB
  • sloc: cpp: 6,538; makefile: 144; sh: 6
file content (83 lines) | stat: -rw-r--r-- 1,987 bytes parent folder | download | duplicates (6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#ifndef BLISS_HEAP_HH
#define BLISS_HEAP_HH

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.
  
  This file is part of bliss.
  
  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

namespace bliss {

/** \internal
 * \brief A capacity bounded heap data structure.
 */

class Heap
{
  unsigned int N;
  unsigned int n;
  unsigned int *array;
  void upheap(unsigned int k);
  void downheap(unsigned int k);
public:
  /**
   * Create a new heap.
   * init() must be called after this.
   */
  Heap() {array = 0; n = 0; N = 0; }
  ~Heap();

  /**
   * Initialize the heap to have the capacity to hold \e size elements.
   */
  void init(const unsigned int size);

  /**
   * Is the heap empty?
   * Time complexity is O(1).
   */
  bool is_empty() const {return(n==0); }

  /**
   * Remove all the elements in the heap.
   * Time complexity is O(1).
   */
  void clear() {n = 0;}

  /**
   * Insert the element \a e in the heap.
   * Time complexity is O(log(N)), where N is the number of elements
   * currently in the heap.
   */
  void insert(const unsigned int e);

  /**
   * Remove and return the smallest element in the heap.
   * Time complexity is O(log(N)), where N is the number of elements
   * currently in the heap.
   */
  unsigned int remove();

  /**
   * Get the number of elements in the heap.
   */
  unsigned int size() const {return n; }
};

} // namespace bliss

#endif