Talk:Weak heap

Binary?

Are all weak heaps necessarily binary heaps? Or just heaps? Andy Dingley (talk) 10:27, 2 December 2015 (UTC)

Weak heaps are not heap-ordered trees at all. In a heap-ordered tree, all children must be smaller or equal (for a max-heap), while in a weak heap this is true only of one of the two children. But I think they are all based on binary trees rather than higher order trees. —David Eppstein (talk) 14:55, 2 December 2015 (UTC)

@Andy Dingley and David Eppstein: Actually, weak heaps are heap-ordered trees, and that's the best way to think of them. But they're not binary trees. They're multi-way trees, represented using binary trees in a "right-child left-sibling" form. So an element is higher priority than its first child (binary right child) and all of its first child's siblings, but not necessarily higher priority than it sibling (binary left child).

I've tried to seriously overhaul the explanation, placing more emphasis on the multi-way tree model, and I'd really appreciate some other eyes to tell me if I've improved things or made a mess of it. After some careful study, I understand them, but I'm so far down in the details that I'm having a hard time thinking about the overview. Could either of you have a look and tell me how the forest looks which I am unable to see through the trees? 71.41.210.146 (talk) 02:40, 30 December 2016 (UTC)

Hyphenation

@Widefox: The main reason I think the hyphenated version does not belong in the lead is that the difference between "Weak heap" and "weak-heap" is too trivial to need clarification to the reader in the lead. They are not significantly different and thus not a significant alternative name that needs to be presented in the lead.

In the examples at WP:OTHERNAMES and MOS:LEADALT. the other names are included because they're not self-evident. E.g. Mercury and quicksilver, or Danzig and Gdansk. But there's no need to e.g. name a person both with and without their middle name; readers understand abbreviation by omitting parts of a name. The closest is noting that company names are stylized with certain capitalizations (like Cirrus (interbank network)), or that Franklin Delano Roosevelt is widely known as FDR.

Certainly weak-heap should redirect to weak heap, but including both variants in the lead is WP:LEADCLUTTER.

As for "weak-heap sort" used later in the article, that's a standard English-language hyphenated compound modifier (discussed in more general terms at compound modifier); the hyphen makes clear that it's the heap that's weak and not the sort. It's like the relationship of red lights to red-light districts: the hyphen makes clear which noun the adjective applies to. 104.153.72.218 (talk) 15:27, 30 July 2017 (UTC)

Weak-heap redirect  Done. I'm clearly in the minority here out the three of us, with User:David Eppstein also undoing the inclusion of the alternative title (and I would defer to him on content in these topics...), but... as our primary (Dutton) and other main sources [1] etc use the hyphenated version, I think it's useful for readers. I can see how the sort may be different anyhow, but sources use the hyphen for the heap as well as the sort. Wikipedia:OTHERNAMES When this title is a name, significant alternative names for the topic should be mentioned in the article, usually in the first sentence or paragraph. These may include alternative spellings, so this significant alternative spelling should be mentioned in the first sentence. Widefox; talk 18:43, 30 July 2017 (UTC)

I reverted it because I found the justification unconvincing. In the phrase "weak-heap sort", the hyphen is used merely to mean that this is ((weak heap) sort), not (weak (heap sort)); this sort of disambiguation of grouping does not imply anything about whether the hyphen should be kept when there are only two words. To me, "weak-heap" looks like the sort of thing that would be written by a non-native English speaker (probably in this case German) importing punctuation rules from a different language. —David Eppstein (talk) 18:50, 30 July 2017 (UTC)

@David Eppstein and Widefox: Widefox is quite right that Dutton's original paper uses the hyphenated form, and while I don't now much about him, "Ronald Dutton" sounds like a name English-speaking parents would choose, and the English in the paper doesn't seem stilted. Still, his specialty is computer science, not writing or literature. My two points are:

1. Despite that early usage, the non-hyphenated "weak heap" is the more widely used form, so if it comes to a choice about common name, that's the one that should be chosen. I don't feel any regret about this, as it's quite common that the preferred terminology evolves later than the first description of a concept. (Famously, the earliest editions of Darwin's famous book do not include the word "evolution". Newton's laborious calculus notation also comes to mind.)
2. The relationship between the two forms is so glaringly obvious that there's no need to even point it out. Including the hyphen or not is like a capitalization variant. If there were some difference between a Weak Heap, Weak-Heap, weak heap or weak-heap I'd want to draw attention to the subtle distinction, because otherwise a reader sould be unlikely to even notice that there was a difference.

The article at Aix la Chapelle only mentions the hyphenated form Aix-la-Chapelle, and I don't think there's any reason to change that, even though both farms are in reasonably common use. 104.153.72.218 (talk) 19:37, 30 July 2017 (UTC)

User:David Eppstein the justification isn't the name of the sort or about the commonname, but a valid and widely used spell variant for the heap per Dutton and others. That meets OTHERNAMES alt spellings. didn't think this would be controversial as it's in our main sources here, do think useful, but trivial, so leaving. IP editor - as for other articles with many alt names in different languages, well, comparing an abundance with a paucity isn't convincing as we have a limit to prevent lede clutter. (p.s. I'm aware we defer to our spelling conventions rather than the spelling of experts in a field). Widefox; talk 22:43, 30 July 2017 (UTC)

@Widefox: I'm afraid I can't understand what you are trying to say here. "comparing an abundance with a paucity" of what?

It appears that you are making an argument based on belief that a hyphenation difference is a spelling difference. While they are both forms of orthography, this is not true; punctuation is not spelling. There is no spelling difference between eBay and , between E. E. Cummings and e e cummings, between et cetera and et cetera, or between 𝔐𝔢𝔦𝔫 𝔎𝔞𝔪𝔭𝔣 and Mein Kampf. "saccharomyces cerevisiae" is correctly spelled, even though typographical conventions in biology state that binomial names are properly written in italics, with the genus name capitalized.

To meet the "significant alternative names" criterion in WP:OTHERNAMES, a name must be both significantly used and significantly different. If you search for "stylized as", you'll see that kind of variants which qualify for a mention in the lead: significantly unconventional letter case or (rarely) punctuation.

For examples of articles that use both hyphenated and non-hyphenated forms without distinction, consider:

• Stow-on-the-Wold (even though the town council web site omits the hyphens)
• High-level design
• High-altitude nuclear explosion
• Free fall
• Impedance matching

I'm sure there are many more, but finding them required laborious manual search. 104.153.72.218 (talk) 10:01, 1 August 2017 (UTC)

User:104.153.72.218 Yes, to clarify, "...of alternative names" ... Comparing an article with many alternative titles with one with none may not be a valid comparison as, for example, we place a limit on the number of alternative names in the lede (per LEADCLUTTER). Those examples are slightly different as they are stylized, but per the non-spelling logic, provide some backing for my point eBay (...stylized as ebay), E. E. Cummings, i.e. both are included despite having the same spelling. (Although if I remember correctly, our treatment of eBay is of an explicit exceptional nature in the MOS, so also may not be a good example to take per se). Those examples do put weight on the primary source with a different variant (irrelevant of my imprecise use of "spelling"). Can you point to where that criterion comes from please, as I can't see it in WP:OTHERNAMES.

There's many sources over Dutton: [2] [3] [4] [5] [6] [7] [8] [9] ...

WP:LEADCLUTTER clearly doesn't apply as one alternative name is clearly not above the threshold ..three alternate names...

A more similar example is Shellsort, also known as Shell sort.... Widefox; talk 11:57, 1 August 2017 (UTC)