Thread: Different MultiSet and Heap

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    116

    Question Different MultiSet and Heap

    I don't know what different in C++ between this data structure. I know that MultiSet is a set that has many same keys, and Heap is like binary Search Tree. MultiSet/Set, I have read that C++ use interval tree for this data structure. So, what is real different between MultiSet and Heap in C++.
    thanks

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The only "heap" I know of in C++ is the algorithms: make_heap, push_heap, pop_heap, sort_heap. These are meant to be used on a vector, and enforce the properties of a heap data structure. If you don't know what a heap data structure is, you should look that up. Also, the priority_queue uses a heap structure.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Refer to your DADS:

    bag (multiset): An unordered collection of values that may have duplicates.

    heap: A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    A heap is not like a binary search tree. Yes internally it has a notion of parent/child relationships and a multiset may be implemented that way, but that's about where the similarity ends. Externally a Binary Search Tree has O(log n) search time whereas a heap doesn't support searching so it would take O(n). A heap can tell you the minimum item immediately. A binary search tree may have to visit a lot of nodes to do so. A BST allows you to visit all items in sorted order but a heap cannot do that at all. A heap requires copying items and moving them around to perform insertion or removals, but a BST doesn't. A heap is very very different from a BST.

    What you're actually doing is comparing a container with a data structure.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multiset stl
    By dpp in forum C++ Programming
    Replies: 3
    Last Post: 03-29-2009, 08:42 AM
  2. making multiset destructor faster...
    By bling in forum C++ Programming
    Replies: 2
    Last Post: 08-30-2008, 11:56 AM
  3. multiset and classes
    By quizkiwi in forum C++ Programming
    Replies: 10
    Last Post: 08-30-2004, 06:08 PM
  4. Anyone Know HEAP ?
    By Kam in forum C Programming
    Replies: 5
    Last Post: 09-14-2002, 07:47 AM
  5. heap
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-10-2001, 02:15 PM