Структура података гомиле

У овом упутству ћете научити шта је структура података гомиле. Такође, наћи ћете радне примере операција гомиле на Ц, Ц ++, Јава и Питхон.

Структура података гомиле је комплетно бинарно стабло које задовољава својство гомиле . Такође се назива и бинарна гомила .

Комплетно бинарно стабло је посебно бинарно стабло у коме

  • попуњен је сваки ниво, осим евентуално последњег
  • сви чворови су што даље лево

Својство гомиле је својство чвора у коме

  • (за максималну хрпу) кључ сваког чвора је увек већи од његовог подређеног чвора, а кључ коренског чвора је највећи међу свим осталим чворовима;
  • (за мин хеап) кључ сваког чвора је увек мањи од подређених чворова, а кључ коренског чвора је најмањи међу свим осталим чворовима.

Операције гомиле

Неке од важних операција изведених на гомили су описане у наставку заједно са њиховим алгоритмима.

Хеапифи

Хеапифи је процес стварања структуре података гомиле од бинарног стабла. Користи се за стварање Мин-Хеап или Мак-Хеап.

  1. Нека улазни низ буде
  2. Направите комплетно бинарно стабло од низа
  3. Почните од првог индекса нелистног чвора чији је индекс дат са n/2 - 1.
  4. Поставите тренутни елемент iкао largest.
  5. Индекс левог детета дат је са, 2i + 1а десног детета са 2i + 2.
    Ако leftChildје веће од currentElement(тј. Елемент у ithиндексу), постави leftChildIndexкао највећи.
    Ако rightChildје веће од елемента у largest, поставите rightChildIndexкао largest.
  6. Замените largestсаcurrentElement
  7. Поновите кораке 3-7 док се подстабла такође не појачају.

Алгоритам

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Да бисте креирали Мак-Хеап:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

За Мин-Хеап, оба leftChildи rightChildморају бити мања од надређене за све чворове.

Уметните елемент у гомилу

Алгоритам за уметање у Мак Хеап

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Уметните нови елемент на крај стабла.
  2. Ојачајте дрво.

За Мин Хеап, горњи алгоритам је модификован тако да parentNodeје увек мањи од newNode.

Избриши елемент из гомиле

Алгоритам за брисање у Мак Хеап-у

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Изаберите елемент који желите избрисати.
  2. Замените га последњим елементом.
  3. Уклоните последњи елемент.
  4. Ојачајте дрво.

За Мин Хеап, горњи алгоритам је измењен тако да су оба childNodesвећа од currentNode.

Завири (пронађи макс. / Мин)

Пеек операција враћа максимални елемент из Мак Хеап или минимални елемент из Мин Хеап без брисања чвора.

И за Мак хеап и Мин Хеап

 ретурн роотНоде

Ектрацт-Мак / Мин

Ектрацт-Мак враћа чвор с максималном вриједношћу након уклањања из Мак Хеап-а, док Ектрацт-Мин враћа чвор с минимумом након уклањања из Мин Хеап-а.

Примери Питхон, Јава, Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java import java.util.ArrayList; class Heap ( void heapify(ArrayList hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Апликације за структуру података гомиле

  • Гомила се користи док се имплементира приоритетни ред.
  • Дијкстрин алгоритам
  • Хеап Сорт

Занимљиви Чланци...