Heap data structure

7 Key excerpts on "Heap data structure"

• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  7

  Heaps and Priority Queues

  A Heap data structure is a tree-based data structure in which each node of the tree has a specific relationship with other nodes, and they are stored in a specific order. Depending upon the specific order of the nodes in the tree, heaps can be of different types, such as a min heap and a max heap.

  A priority queue is an important data structure that is similar to the queue and stack data structures that stores data along with the priority associated with them. In this, the data is served according to the priority. Priority queues can be implemented using an array, linked list, and trees; however, they are often implemented using a heap as it is very efficient.

  In this chapter, we will learn the following:

  • The concept of the Heap data structure and different operations on it
  • Understanding the concept of the priority queue and its implementation using Python

  Heaps

  A Heap data structure is a specialization of a tree in which the nodes are ordered in a specific way. A heap is a data structure where each data elements satisfies a heap property, and the heap property states that there must be a certain relationship between a parent node and its child nodes. According to this certain relationship in the tree, the heaps can be of two types, in other words, max heaps and min heaps. In a max heap, each parent node value must always be greater than or equal to all its children. In this kind of tree, the root node must be the greatest value in the tree. For example, see Figure 7.1 showing the max heap in which all the nodes have greater values compared to their children:

  Figure 7.1: An example of a max heap

  In a min heap, the relationship between parent and children is that the value of the parent node must always be less than or equal to its children. This rule should be followed by all the nodes in the tree. In the min heap, the root node holds the lowest value. For example, see Figure 7.2 showing the min

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in C++

  • Michael T. Goodrich, Roberto Tamassia, David M. Mount(Authors)
  • 2011(Publication Date)
  • Wiley

    (Publisher)

  This approach is, in fact, exactly what we can achieve using the priority-queue implementation discussed in this section. An efficient realization of a priority queue uses a data structure called a heap. This data structure allows us to perform both insertions and removals in logarith- mic time, which is a significant improvement over the list-based implementations discussed in Section 8.2. The fundamental way the heap achieves this improvement is to abandon the idea of storing elements and keys in a list and take the approach of storing elements and keys in a binary tree instead. 8.3.1 The Heap data structure A heap (see Figure 8.3) is a binary tree T that stores a collection of elements with their associated keys at its nodes and that satisfies two additional properties: a relational property, defined in terms of the way keys are stored in T , and a structural property, defined in terms of the nodes of T itself. We assume that a total order relation on the keys is given, for example, by a comparator. The relational property of T , defined in terms of the way keys are stored, is the following: Heap-Order Property: In a heap T , for every node v other than the root, the key associated with v is greater than or equal to the key associated with v’s parent. As a consequence of the heap-order property, the keys encountered on a path from the root to an external node of T are in nondecreasing order. Also, a minimum key is always stored at the root of T . This is the most important key and is informally said to be “at the top of the heap,” hence, the name “heap” for the data structure. By the way, the Heap data structure defined here has nothing to do with the free- store memory heap (Section 14.1.1) used in the run-time environment supporting programming languages like C++. You might wonder why heaps are defined with the smallest key at the top, rather than the largest.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithms: Design Techniques And Analysis

  Design Techniques and Analysis

  • M H Alsuwaiyel(Author)
  • 1999(Publication Date)
  • World Scientific

    (Publisher)

  In Chapter 4, we investigate in more detail two fundamental data struc- tures that are used for maintaining priority queues and disjoint sets. These two data structures, namely the heap and disjoint set data structures, are used as a building block in the design of many efficient algorithms, espe- cially graph algorithms. In this book, heaps will be used in the design of an efficient sorting algorithm, namely HEAPSORT. We will also make use of heaps in Chapter 8 for designing efficient algorithms for the single-source shortest path problem, the problem of computing minimum cost spanning trees and the problem of finding variable-length code for data compression. Heaps are also used in branch-and-bound algorithms, which is the subject of Sec. 13.5. The disjoint set data structure will be used in Sec. 8.3 in Algo- rithm KRUSKAL for finding a minimum cost spanning tree of an undirected graph. Both data structures are used extensively in the literature for the design of more complex algorithms. Chapter 1 Basic Concepts in Algorithmic Analysis 1.1 Introduction The most general intuitive idea of an algorithm * is a procedure that consists of a finite set of instructions which, given an input from some set of possible inputs, enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions. The set of possible inputs consists of all inputs to which the algorithm gives an output. If there is an output for a particular input, then we say that the algorithm can be applied to this input and process it to give the corresponding output. We require that an algorithm halts on every input, which implies that each instruction requires a finite amount of time, and each input has a finite length.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Advanced Data Structures

  • Peter Brass(Author)
  • 2008(Publication Date)
  • Cambridge University Press

    (Publisher)

  5 Heaps Heaps are, after the search trees, the second most studied type of data structure. As abstract structure they are also called priority queues, and they keep track of a set of objects, each object having a key value (the priority), and support the operations to insert an object, find the object of minimum key (find min), and delete the object of minimum key (delete min). So unlike the search trees, there are neither arbitrary find operations nor arbitrary delete operations possible. Of course, we can replace everywhere the minimum by maximum; where this distinction is important, one type is called the min-heap and the other the max-heap. If we need both types of operations, the structure is called a double-ended heap, which is a bit more complicated. The heap structure was originally invented by Williams 1 (1964) for the very special application of sorting, although he did already present it as a separate data structure with possibly further applications. But it was recognized only much later that heaps have many other, and indeed more important, applica- tions. Still, the connection to sorting is important because the lower bound of (n log n) on comparison-based sorting of n objects implies a lower bound on the complexity of the heap operations. We can sort by first inserting all objects in the heap and then performing find min and delete min operations to recover the objects, sorted in increasing order. So we can sort by performing n operations each of insert, find min, and delete min; thus, at least one of these operations must have (in a comparison-based model) a complexity (log n). This connection works in both directions; there is an equivalence between the speed of sorting and heap operations in many models – even those 1 Usually Floyd (1964) is also cited, but his contribution is the adaptation of the heap to in-place sorting, continuing the line of development of his Treesort algorithm (Floyd 1962) previously improved by Kaupe (1962). 209

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Objects, Abstraction, Data Structures and Design

  Using C++

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  In these cases, the loop terminates (line 6 or 13). This is shown in Figure 8.33. At this point the heap property is restored, and the next smallest item can be removed from the heap. Performance of the Heap The remove algorithm traces a path from the root to a leaf, and the insert algorithm traces a path from a leaf to the root. This requires at most h steps, where h is the height of the tree. The largest heap of height h is a full tree of height h. This tree has 2 h – 1 nodes. The smallest heap of height h is a complete tree of height h, consist- ing of a full tree of height h – 1, with a single node as the left child of the leftmost child at height h – 1. Thus, this tree has 2 (h – 1) nodes. Therefore, both insert and remove are O(log n), where n is the number of items in the heap. Priority Queues In computer science, a heap is used as the basis of a very efficient algorithm for sort- ing arrays, called heapsort, which you will study in Chapter 10. The heap is also used to implement a special kind of queue called a priority queue. Sometimes a FIFO (First-In-First-Out) queue may not be the best way to implement a waiting line. In a print queue you might want to print a short document before some longer documents that were ahead of the short document in the queue. For example, if you were waiting by the printer for a single page to print, it would be very frustrating to have to wait until several documents of 50 pages or more were printed just because they entered the queue before yours did. Therefore, a better way to implement a print queue would be to use a priority queue. A priority queue 8.5 Heaps and Priority Queues 489 is a data structure in which only the highest-priority item is accessible. During inser- tion, the position of an item in the queue is based on its priority relative to the pri- orities of other items in the queue.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Big C++

  Late Objects

  • Cay S. Horstmann(Author)
  • 2017(Publication Date)
  • Wiley

    (Publisher)

  17.2 Heaps 557 WORKED EXAMPLE 17.1 Simulating a Queue of Waiting Customers Learn how to use a queue to simulate a line of waiting customers. See your E-Text or visit wiley.com/go/bclo3. 17.2 Heaps A heap (or, for greater clarity, max-heap) is a binary tree with two special properties: 1. A heap is almost complete: all nodes are filled in, except the last level may have some nodes missing toward the right (see Figure 1). 2. The tree fulfills the heap property: all nodes store values that are at least as large as the values stored in their descendants (see Figure 2). Jack Hollingsworth/Photodisc/Getty Images. A heap is an almost complete tree in which the values of all nodes are at least as large as those of their descendants. Figure 1 An Almost Complete Tree Some nodes missing toward the right All nodes filled in Figure 2 A Heap 80 25 57 16 10 43 29 7 9 4 558 Chapter 17 Priority Queues and Heaps It is easy to see that the heap property ensures that the tree’s largest element is stored in the root. A heap is superficially similar to a binary search tree, but there are two important differences: 1. The shape of a heap is very regular. Binary search trees can have arbitrary shapes. 2. In a heap, the left and right subtrees both store elements that are smaller than the root ele- ment. In contrast, in a binary search tree, smaller elements are stored in the left subtree and larger elements are stored in the right subtree. In an almost complete tree, all layers but one are completely filled. Suppose we have a heap and want to insert a new element. After the insertion, the heap property should again be fulfilled. The following algorithm carries out the insertion (see Figure 3). 1. First, add a vacant slot to the end of the tree. 2. Next, demote the parent of the empty slot if it is smaller than the element to be inserted. That is, move the parent value into the vacant slot, and move the vacant slot up.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Java

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  338 Chapter 9. Heaps and Priority Queues 9.3 Heaps The two strategies for implementing a priority queue ADT in the previous section demonstrate an interesting trade-off. When using an unsorted list to store entries, we can perform insertions in O(1) time, but finding or removing an element with minimal key requires an O(n)-time loop through the entire collection. In contrast, if using a sorted list, we can trivially find or remove the minimal element in O(1) time, but adding a new element to the queue may require O(n) time to restore the sorted order. In this section, we provide a more efficient realization of a priority queue using a data structure called a binary heap. This data structure allows us to perform both insertions and removals in logarithmic time, which is a significant improvement over the list-based implementations discussed in Section 9.2. The fundamental way the heap achieves this improvement is to use the structure of a binary tree to find a compromise between elements being entirely unsorted and perfectly sorted. 9.3.1 The Heap data structure A heap (see Figure 9.1) is a binary tree T that stores entries at its positions, and that satisfies two additional properties: a relational property defined in terms of the way keys are stored in T and a structural property defined in terms of the shape of T itself. The relational property is the following: Heap-Order Property: In a heap T , for every position p other than the root, the key stored at p is greater than or equal to the key stored at p’s parent. As a consequence of the heap-order property, the keys encountered on a path from the root to a leaf of T are in nondecreasing order. Also, a minimal key is always stored at the root of T . This makes it easy to locate such an entry when min or removeMin is called, as it is informally said to be “at the top of the heap” (hence, the name “heap” for the data structure).

  Sign up to read

  Learn more about book