Ternary heap - Data Structures

A diagram of a min ternary heap.

A diagram of a min ternary heap.

A ternary heap is a data structure in computer science. It is part of the heap family. It inherits the from ternary tree and the heap. Often there are two kinds of ternary heaps: the min ternary heap and the maxternary heap.

  • Min Ternary Heap
  • As illustrated, a min ternary heap has the smallest element as its root. Parent node has to be smaller than or equal to its children.
  • Max Ternary Heap
  • A max ternary heap has the biggest element as its root. Each node has to be greater than or equal to its children.

In both cases, a ternary heap has to satisfy the heap property, which is every level of tree has to be filled, or if the last level is not filled, the leaves are distributed from left to right. These rules has to be strictly followed when implementing the code to build a ternary heap.

Heapify

The process of building a heap is called Heapify. A way to implement this data structure is to use a collection, e.g.: Vectors in Java.

Each element in the collection is a node of the ternary heap, where the index is in the order of from top to bottom, from left to right.

The example max ternary heap in a Vector will be like this:

[99, 63, 56, 88, 10, 53, 42, 36, 18, 39]

For each node, assuming that its index is i, and that indexing starts with node 0

  • parent's index: FORMULA
  • left child's: FORMULA
  • middle child's: FORMULA
  • right child's: FORMULA

The following C-like pseudocode shows how to heapify a vector to a max ternary heap.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structures Topics