Category:Disjoint set data structure

From LiteratePrograms
Jump to: navigation, search

A disjoint set data structure, also known as a union-find set, is a data structure that keeps track of a partitioning of a set of elements over time as certain operations are done. The three main operations are:

  • MakeSet: Create a new partition containing a single given element.
  • Find: Figure out which partition a given element is in.
  • Merge/Union: Merge two partitions into a single partition.

There are several solutions to this problem. The most efficient known and most commonly used is disjoint set forests with path compression and the union rank heuristic, which has a performance of O(α(n)) amortized time per operation, where α(n) is a very slowly growing function that for all practical purposes never exceeds 5.


Pages in category "Disjoint set data structure"

This category contains only the following page.